{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:41:30Z","timestamp":1725745290585},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642403279"},{"type":"electronic","value":"9783642403286"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40328-6_13","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T13:17:34Z","timestamp":1376659054000},"page":"173-188","source":"Crossref","is-referenced-by-count":4,"title":["Multiple Traveling Salesmen in Asymmetric Metrics"],"prefix":"10.1007","author":[{"given":"Zachary","family":"Friggstad","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"An, H.-C., Kleinberg, R., Shmoys, D.B.: Improving christofides\u2019 algorithm for the s-t path TSP. In: Proceedings of ACM Symposium on Theory of Computing, pp. 875\u2013886 (2012)","DOI":"10.1145\/2213977.2214055"},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"Asadpour, A., Goemans, M.X., Madry, A., Oveis Gharan, S., Saberi, A.: An O(logn\/ loglogn)-approximation algorithm for the asymmetric traveling salesman problem. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms, pp. 379\u2013389 (2010)","DOI":"10.1137\/1.9781611973075.32"},{"key":"13_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/978-3-642-15369-3_3","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"M. Bateni","year":"2010","unstructured":"Bateni, M., Chuzhoy, J.: Approximation algorithms for the directed k-tour and k-stroll problems. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX and RANDOM 2010. LNCS, vol.\u00a06302, pp. 25\u201338. Springer, Heidelberg (2010)"},{"issue":"4","key":"13_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1383369.1383378","volume":"4","author":"M. Blaser","year":"2008","unstructured":"Blaser, M.: A new approximation algorithm for the asymmetric TSP with triangle inequality. ACM Trans. Algorithms\u00a04(4), 47:1\u201347:15 (2008)","journal-title":"ACM Trans. Algorithms"},{"key":"13_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/978-3-642-20807-2_8","volume-title":"Integer Programming and Combinatoral Optimization","author":"D. Chakrabarty","year":"2011","unstructured":"Chakrabarty, D., Swamy, C.: Facility location with client latencies: Linear programming based techniques for minimum latency problems. In: G\u00fcnl\u00fck, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol.\u00a06655, pp. 92\u2013103. Springer, Heidelberg (2011)"},{"issue":"1","key":"13_CR6","doi-asserted-by":"publisher","first-page":"197","DOI":"10.4086\/toc.2007.v003a010","volume":"3","author":"C. Chekuri","year":"2007","unstructured":"Chekuri, C., P\u00e1l, M.: An O(logn) approximation ratio for the asymmetric traveling salesman path problem. Theory of Computing\u00a03(1), 197\u2013209 (2007)","journal-title":"Theory of Computing"},{"key":"13_CR7","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie Mellon University (1976)"},{"key":"13_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/978-3-540-74208-1_8","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"U. Feige","year":"2007","unstructured":"Feige, U., Singh, M.: Improved approximation ratios for traveling salesperson tours and paths in directed graphs. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) APPROX and RANDOM 2007. LNCS, vol.\u00a04627, pp. 104\u2013118. Springer, Heidelberg (2007)"},{"issue":"1","key":"13_CR9","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1002\/net.3230120103","volume":"12","author":"A.M. Frieze","year":"1982","unstructured":"Frieze, A.M., Galbiati, G., Maffioli, F.: On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks\u00a012(1), 23\u201339 (1982)","journal-title":"Networks"},{"key":"13_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/978-3-642-36694-9_16","volume-title":"Integer Programming and Combinatorial Optimization","author":"Z. Friggstad","year":"2013","unstructured":"Friggstad, Z., Gupta, A., Singh, M.: An improved integrality gap for asymmetric TSP paths. In: Goemans, M., Correa, J. (eds.) IPCO 2013. LNCS, vol.\u00a07801, pp. 181\u2013192. Springer, Heidelberg (2013)"},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Friggstad, Z., Salavatipour, M.R., Svitkina, Z.: Asymmetric traveling salesman path and directed latency problems. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pp. 419\u2013428 (2010); Full version: manuscript number 0907.0726 on arXiv","DOI":"10.1137\/1.9781611973075.35"},{"key":"13_CR12","volume-title":"Computers and Intractability; A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1990","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1990)"},{"key":"13_CR13","doi-asserted-by":"publisher","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","volume":"18","author":"M. Held","year":"1970","unstructured":"Held, M., Karp, R.M.: The Traveling-Salesman Problem and Minimum Spanning Trees. Operations Research\u00a018, 1138\u20131162 (1970)","journal-title":"Operations Research"},{"issue":"5","key":"13_CR14","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0167-6377(91)90016-I","volume":"10","author":"J.A. Hoogeveen","year":"1991","unstructured":"Hoogeveen, J.A.: Analysis of christofides\u2019 heuristic: Some paths are more difficult than cycles. Oper. Res. Lett.\u00a010(5), 291\u2013295 (1991)","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"13_CR15","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1145\/1082036.1082041","volume":"52","author":"H. Kaplan","year":"2005","unstructured":"Kaplan, H., Lewenstein, M., Shafrir, N., Sviridenko, M.: Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. J. ACM\u00a052(4), 602\u2013626 (2005)","journal-title":"J. ACM"},{"key":"13_CR16","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Lampis, M., Schmied, R.: New inapproximability bounds for TSP. CoRR, abs\/1303.6437 (2013)","DOI":"10.1007\/978-3-642-45030-3_53"},{"issue":"1","key":"13_CR17","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s10107-006-0046-8","volume":"113","author":"F. Lam","year":"2008","unstructured":"Lam, F., Newman, A.: Traveling salesman path problems. Math. Program.\u00a0113(1), 39\u201359 (2008)","journal-title":"Math. Program."},{"key":"13_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/978-3-540-74208-1_19","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"V. Nagarajan","year":"2007","unstructured":"Nagarajan, V., Ravi, R.: Poly-logarithmic approximation algorithms for directed vehicle routing problems. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) APPROX and RANDOM 2007. LNCS, vol.\u00a04627, pp. 257\u2013270. Springer, Heidelberg (2007)"},{"key":"13_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/978-3-540-85363-3_16","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"V. Nagarajan","year":"2008","unstructured":"Nagarajan, V., Ravi, R.: The directed minimum latency problem. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 193\u2013206. Springer, Heidelberg (2008)"},{"key":"13_CR20","unstructured":"Rathinam, S., Sengupta, R.: Matroid intersection and its application to a multiple depot, multiple TSP. Technical report, Institute of Transportation Studies, UC Berkeley (2006)"},{"key":"13_CR21","unstructured":"Schrijver, A.: Combinatorial Optimization - Polyhedra and Efficiency. Springer (2003)"},{"key":"13_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1007\/978-3-642-36694-9_31","volume-title":"Integer Programming and Combinatorial Optimization","author":"A. Seb\u0151","year":"2013","unstructured":"Seb\u0151, A.: Eight-fifth approximation for the path TSP. In: Goemans, M., Correa, J. (eds.) IPCO 2013. LNCS, vol.\u00a07801, pp. 362\u2013374. Springer, Heidelberg (2013)"},{"key":"13_CR23","unstructured":"Williamson, D.P.: Analysis of the held-karp heuristic for the traveling salesman problem. Master\u2019s thesis, Massachusetts Institute of Technology, Cambridge, MA, USA (1990)"},{"key":"13_CR24","series-title":"Mathematical Programming Studies","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BFb0120913","volume-title":"Combinatorial Optimization II","author":"L.A. Wolsey","year":"1980","unstructured":"Wolsey, L.A.: Heuristic analysis, linear programming and branch and bound. In: Combinatorial Optimization II. Mathematical Programming Studies, vol.\u00a013, pp. 121\u2013134. Springer, Heidelberg (1980)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40328-6_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T17:42:54Z","timestamp":1558028574000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40328-6_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403279","9783642403286"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40328-6_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}