{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T19:57:20Z","timestamp":1725479840298},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642366932"},{"type":"electronic","value":"9783642366949"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-36694-9_16","type":"book-chapter","created":{"date-parts":[[2013,3,11]],"date-time":"2013-03-11T06:08:39Z","timestamp":1362982119000},"page":"181-192","source":"Crossref","is-referenced-by-count":1,"title":["An Improved Integrality Gap for Asymmetric TSP Paths"],"prefix":"10.1007","author":[{"given":"Zachary","family":"Friggstad","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohit","family":"Singh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"An, H.-C., Kleinberg, R.D., Shmoys, D.B.: Improving Christofides\u2019 algorithm for the s-t path TSP. In: Proc. 44th ACM Symp. on Theory of Computing (2012)","DOI":"10.1145\/2213977.2214055"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Asadpour, A., Goemans, M.X., M\u0105dry, A., Oveis Gharan, S., Saberi. A.: An O(logn\/loglogn)-approximation algorithm for the asymmetric traveling salesman problem. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 379\u2013389. SIAM, Philadelphia (2010)","DOI":"10.1137\/1.9781611973075.32"},{"key":"16_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":"16_CR4","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1145\/1383369.1383378","volume":"4","author":"M. Bl\u00e4ser","year":"2008","unstructured":"Bl\u00e4ser, M.: A new approximation algorithm for the asymmetric TSP with triangle inequality. ACM Trans. Algorithms 4(4), Art. 47, 15 (2008)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"16_CR5","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1287\/moor.1060.0191","volume":"31","author":"M. Charikar","year":"2006","unstructured":"Charikar, M., Goemans, M.X., Karloff, H.: On the integrality ratio for the asymmetric traveling salesman problem. Math. Oper. Res.\u00a031(2), 245\u2013252 (2006)","journal-title":"Math. Oper. Res."},{"key":"16_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 Comput.\u00a03, 197\u2013209 (2007)","journal-title":"Theory Comput."},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Dependent randomized rounding via exchange properties of combinatorial structures. In: FOCS, pp. 575\u2013584 (2010)","DOI":"10.1109\/FOCS.2010.60"},{"key":"16_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":"16_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":"16_CR10","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1137\/1.9781611973075.35","volume-title":"Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Z. Friggstad","year":"2010","unstructured":"Friggstad, Z., Salavatipour, M.R., Svitkina, Z.: Asymmetric traveling salesman path and directed latency problems. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 419\u2013428. SIAM, Philadelphia (2010)"},{"issue":"4","key":"16_CR11","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"},{"issue":"1, Ser. A","key":"16_CR12","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, Ser. A), 39\u201359 (2008)","journal-title":"Math. Program."},{"key":"16_CR13","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":"16_CR14","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":"16_CR15","series-title":"Algorithms and Combinatorics","volume-title":"Combinatorial optimization. Polyhedra and efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial optimization. Polyhedra and efficiency. Algorithms and Combinatorics, vol.\u00a024. Springer, Berlin (2003)"},{"key":"16_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1007\/978-3-642-36694-9_31","volume-title":"IPCO 2013","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":"16_CR17","unstructured":"Seb\u0151, A., Vygen, J.: Shorter tours by nicer ears: 7\/5-approximation for graphic TSP, 3\/2 for the path version, and 4\/3 for two-edge-connected subgraphs. CoRR, abs\/1201.1870 (2012)"}],"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-642-36694-9_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T21:48:02Z","timestamp":1558302482000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-36694-9_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642366932","9783642366949"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-36694-9_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}