{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:51:45Z","timestamp":1781077905699,"version":"3.54.1"},"reference-count":10,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2019,11,26]],"date-time":"2019-11-26T00:00:00Z","timestamp":1574726400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,11,26]],"date-time":"2019-11-26T00:00:00Z","timestamp":1574726400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2020,9]]},"DOI":"10.1007\/s10107-019-01450-8","type":"journal-article","created":{"date-parts":[[2019,11,26]],"date-time":"2019-11-26T16:02:40Z","timestamp":1574784160000},"page":"379-395","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["The asymmetric traveling salesman path LP has constant integrality ratio"],"prefix":"10.1007","volume":"183","author":[{"given":"Anna","family":"K\u00f6hne","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vera","family":"Traub","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jens","family":"Vygen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,11,26]]},"reference":[{"key":"1450_CR1","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/j.endm.2005.05.033","volume":"19","author":"S Boyd","year":"2005","unstructured":"Boyd, S., Elliott-Magwood, P.: Computing the integrality gap of the asymmetric traveling salesman problem. Electron. Notes Discrete Math. 19, 241\u2013247 (2005)","journal-title":"Electron. Notes Discrete Math."},{"key":"1450_CR2","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. 31, 245\u2013252 (2006)","journal-title":"Math. Oper. Res."},{"key":"1450_CR3","first-page":"233","volume":"71","author":"J Edmonds","year":"1967","unstructured":"Edmonds, J.: Optimum branchings. J. Res. Natl. Bur. Std. B 71, 233\u2013240 (1967)","journal-title":"J. Res. Natl. Bur. Std. B"},{"key":"1450_CR4","doi-asserted-by":"crossref","unstructured":"Feige, U., Singh, M.: Improved approximation algorithms for traveling salesperson tours and paths in directed graphs. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) Proceedings of the 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems; LNCS 4627, pp. 104\u2013118. Springer, Berlin (2007)","DOI":"10.1007\/978-3-540-74208-1_8"},{"key":"1450_CR5","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1287\/moor.2015.0752","volume":"41","author":"Z Friggstad","year":"2016","unstructured":"Friggstad, Z., Gupta, A., Singh, M.: An improved integrality gap for asymmetric TSP paths. Math. Oper. Res. 41, 745\u2013757 (2016)","journal-title":"Math. Oper. Res."},{"key":"1450_CR6","doi-asserted-by":"publisher","first-page":"1596","DOI":"10.1137\/100797357","volume":"42","author":"Z Friggstad","year":"2013","unstructured":"Friggstad, Z., Salavatipour, M.R., Svitkina, Z.: Asymmetric traveling salesman path and directed latency problems. SIAM J. Comput. 42, 1596\u20131619 (2013)","journal-title":"SIAM J. Comput."},{"key":"1450_CR7","unstructured":"Gottschalk, C.: Approximation algorithms for the traveling salesman problem in graphs and digraphs. Master\u2019s Thesis, Research Institute for Discrete Mathematics, University of Bonn (2013)"},{"key":"1450_CR8","doi-asserted-by":"crossref","unstructured":"Nagarajan, V., Ravi, R.: The directed minimum latency problem. In: A.\u00a0Goel, K.\u00a0Jansen, J.D.P.\u00a0Rolim, R.\u00a0Rubinfeld, (eds.) Proceedings of the 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems; LNCS 5171, pp. 193\u2013206. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-85363-3_16"},{"key":"1450_CR9","doi-asserted-by":"crossref","unstructured":"Svensson, O.: Approximating ATSP by relaxing connectivity. In: Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015), pp. 1\u201319 (2015)","DOI":"10.1109\/FOCS.2015.10"},{"key":"1450_CR10","doi-asserted-by":"crossref","unstructured":"Svensson, O., Tarnawski, J., V\u00e9gh, L.: A constant-factor approximation algorithm for the asymmetric traveling salesman problem. In: Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC 2018), pp. 204\u2013213 (2018)","DOI":"10.1145\/3188745.3188824"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01450-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-019-01450-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01450-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,25]],"date-time":"2020-11-25T00:26:21Z","timestamp":1606263981000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-019-01450-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,26]]},"references-count":10,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["1450"],"URL":"https:\/\/doi.org\/10.1007\/s10107-019-01450-8","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,26]]},"assertion":[{"value":"31 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 November 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 November 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}