{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:56:08Z","timestamp":1787500568627,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540688860","type":"print"},{"value":"9783540688914","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-68891-4_23","type":"book-chapter","created":{"date-parts":[[2008,5,23]],"date-time":"2008-05-23T09:31:37Z","timestamp":1211535097000},"page":"331-343","source":"Crossref","is-referenced-by-count":17,"title":["A Constant Approximation Algorithm for the a priori Traveling Salesman Problem"],"prefix":"10.1007","author":[{"given":"David","family":"Shmoys","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kunal","family":"Talwar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"23_CR1","unstructured":"Jaillet, P.: Probabilistic traveling salesman problems. Technical Report 185, Operations Research Center, MIT (1985)"},{"key":"23_CR2","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1287\/opre.36.6.929","volume":"36","author":"P. Jaillet","year":"1988","unstructured":"Jaillet, P.: A priori solution of a traveling salesman problem in which a random subset of the customers are visited. Operations Research\u00a036, 929\u2013936 (1988)","journal-title":"Operations Research"},{"key":"23_CR3","unstructured":"Bertsimas, D.: Probabilistic Combinatorial Optimization Problems. PhD thesis, MIT, Cambridge, Mass (1988)"},{"issue":"6","key":"23_CR4","doi-asserted-by":"crossref","first-page":"1019","DOI":"10.1287\/opre.38.6.1019","volume":"38","author":"D.J. Bertsimas","year":"1990","unstructured":"Bertsimas, D.J., Jaillet, P., Odoni, A.R.: A priori optimization. Operations Research\u00a038(6), 1019\u20131033 (1990)","journal-title":"Operations Research"},{"key":"23_CR5","doi-asserted-by":"crossref","unstructured":"Schalekamp, F., Shmoys, D.B.: Algorithms for the universal and a priori TSP. Operations Research Letters (in press, 2007)","DOI":"10.1016\/j.orl.2007.04.009"},{"issue":"4","key":"23_CR6","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0167-6377(82)90012-8","volume":"1","author":"J.J. Bartholdi III","year":"1981","unstructured":"Bartholdi III, J.J., Platzman, L.K.: An O(N log N) planar travelling salesman heuristic based on spacefilling curves. Operations Research Letters\u00a01(4), 121\u2013125 (1981\/82)","journal-title":"Operations Research Letters"},{"key":"23_CR7","doi-asserted-by":"publisher","first-page":"649","DOI":"10.1145\/1109557.1109628","volume-title":"Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"M.T. Hajiaghayi","year":"2006","unstructured":"Hajiaghayi, M.T., Kleinberg, R., Leighton, T.: Improved lower and upper bounds for universal tsp in planar metrics. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 649\u2013658. ACM Press, New York (2006)"},{"key":"23_CR8","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1109\/SFCS.2003.1238233","volume-title":"Proceedings of the 44th Anuual IEEE Symposium on Foundations of Computer Science","author":"A. Gupta","year":"2003","unstructured":"Gupta, A., Kumar, A., P\u00e1l, M., Roughgarden, T.: Approximation via cost-sharing: a simple approximation algorithm for the multicommodity rent-or-buy problem. In: Proceedings of the 44th Anuual IEEE Symposium on Foundations of Computer Science, Silver Spring, MD, pp. 606\u2013615. IEEE Computer Society, Los Alamitos (2003)"},{"key":"23_CR9","doi-asserted-by":"crossref","unstructured":"Gupta, A., P\u00e1l, M., Ravi, R., Sinha, A.: Boosted sampling: approximation algorithms for stochastic optimization. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 265\u2013274 (2004)","DOI":"10.1145\/1007352.1007419"},{"key":"23_CR10","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1016\/j.orl.2007.02.005","volume":"35","author":"D.P. Williamson","year":"2007","unstructured":"Williamson, D.P., van Zuylen, A.: A simpler and better derandomization of an approximation algorithm for single source rent-or-buy. Operations Research Letters\u00a035, 707\u2013712 (2007)","journal-title":"Operations Research Letters"},{"key":"23_CR11","unstructured":"Garg, N., Gupta, A., Leonardi, S., Sankowski, P.: Private communication (2007)"},{"key":"23_CR12","first-page":"942","volume-title":"Proceedings of the 19th Anuual ACM-SIAM Symposium on Discrete Algorithms","author":"N. Garg","year":"2008","unstructured":"Garg, N., Gupta, A., Leonardi, S., Sankowski, P.: Stochastic analyses for online combinatorial optimization problems. In: Proceedings of the 19th Anuual ACM-SIAM Symposium on Discrete Algorithms, pp. 942\u2013951. ACM and SIAM, New York and Philadelphia (2008)"},{"key":"23_CR13","volume-title":"The Traveling Salesman Problem","year":"1985","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B. (eds.): The Traveling Salesman Problem. Wiley, Chichester (1985)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-68891-4_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T00:17:51Z","timestamp":1620001071000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-68891-4_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540688860","9783540688914"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-68891-4_23","relation":{},"subject":[]}}