{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T17:50:49Z","timestamp":1710352249239},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2010,8,18]],"date-time":"2010-08-18T00:00:00Z","timestamp":1282089600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2011,10]]},"DOI":"10.1007\/s00224-010-9289-0","type":"journal-article","created":{"date-parts":[[2010,8,17]],"date-time":"2010-08-17T04:32:54Z","timestamp":1282019574000},"page":"615-631","source":"Crossref","is-referenced-by-count":1,"title":["Approximating the Metric TSP in Linear Time"],"prefix":"10.1007","volume":"49","author":[{"given":"Davide","family":"Bil\u00f2","sequence":"first","affiliation":[]},{"given":"Luca","family":"Forlizzi","sequence":"additional","affiliation":[]},{"given":"Guido","family":"Proietti","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,8,18]]},"reference":[{"issue":"2","key":"9289_CR1","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/net.1024","volume":"38","author":"T. Andreae","year":"2001","unstructured":"Andreae, T.: On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality. Networks 38(2), 59\u201367 (2001)","journal-title":"Networks"},{"issue":"5","key":"9289_CR2","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753\u2013782 (1998)","journal-title":"J. ACM"},{"key":"9289_CR3","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/S0020-0190(00)00089-2","volume":"75","author":"H.-J. B\u00f6ckenhauer","year":"2000","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Klasing, R., Seibert, S., Unger, W.: Approximation algorithms for the TSP with sharpened triangle inequality. Inf. Process. Lett. 75, 133\u2013138 (2000)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"9289_CR4","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1287\/moor.23.3.613","volume":"23","author":"R.E. Burkard","year":"1998","unstructured":"Burkard, R.E., Deineko, V.G., Woeginger, G.J.: The travelling salesman and the PQ-tree. Math. Oper. Res. 23(3), 613\u2013623 (1998)","journal-title":"Math. Oper. Res."},{"key":"9289_CR5","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. Technical report, Graduate School of Industrial Administration, Carnegy-Mellon University (1976)"},{"key":"9289_CR6","unstructured":"Czumaj, A., Muthukrishnan, S.M., Rubinfeld, R., Sohler, C. (eds.) Sublinear Algorithms, 17.07.\u201322.07.2005, Dagstuhl Seminar Proceedings, vol.\u00a005291. Internationales Begegnungs- und Forschungszentrum f\u00fcr Informatik (IBFI), Schloss Dagstuhl, Germany (2006)"},{"key":"9289_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1007\/978-3-540-72845-0_11","volume-title":"Proc. of the 6th Workshop on Experimental Algorithms (WEA)","author":"V.G. Deineko","year":"2007","unstructured":"Deineko, V.G., Tiskin, A.: Fast minimum-weight double-tree shortcutting for metric TSP. In: Proc. of the 6th Workshop on Experimental Algorithms (WEA). Lecture Notes in Computer Science, vol.\u00a04525, pp.\u00a0136\u2013149. Springer, Berlin (2007)"},{"key":"9289_CR8","doi-asserted-by":"crossref","unstructured":"Deineko, V.G., Tiskin, A.: Fast minimum-weight double-tree shortcutting for metric TSP: Is the best one good enough? ACM J. Exp. Algorithmics 14 (2009)","DOI":"10.1145\/1498698.1594232"},{"key":"9289_CR9","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/j.endm.2009.02.004","volume":"32","author":"V.G. Deineko","year":"2009","unstructured":"Deineko, V.G., Tiskin, A.: Min-weight double-tree shortcutting for metric TSP: Bounding the approximation ratio. Electron. Notes Discrete Math. 32, 19\u201326 (2009)","journal-title":"Electron. Notes Discrete Math."},{"issue":"1","key":"9289_CR10","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1145\/1077464.1077472","volume":"1","author":"D.E. Drake Vinkemeier","year":"2005","unstructured":"Drake Vinkemeier, D.E., Hougardy, S.: A linear-time approximation algorithm for weighted matchings in graphs. ACM Trans. Algorithms 1(1), 107\u2013122 (2005)","journal-title":"ACM Trans. Algorithms"},{"key":"9289_CR11","doi-asserted-by":"crossref","unstructured":"Gabow, H.N.: An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In: Proc. of the 15th Annual ACM Symp. on Theory of Computing (STOC), pp.\u00a0448\u2013456 (1983)","DOI":"10.1145\/800061.808776"},{"issue":"4","key":"9289_CR12","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1145\/115234.115366","volume":"38","author":"H.N. Gabow","year":"1991","unstructured":"Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for general graph-matching problems. J. ACM 38(4), 815\u2013853 (1991)","journal-title":"J. ACM"},{"key":"9289_CR13","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Sublinear time algorithms for metric space problems. In: Proc. of the 31st Annual ACM Symp. on Theory of Computing (STOC), pp. 428\u2013434 (1999)","DOI":"10.1145\/301250.301366"},{"issue":"1","key":"9289_CR14","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/s12532-009-0002-8","volume":"1","author":"V. Kolmogorov","year":"2009","unstructured":"Kolmogorov, V.: Blossom V: a new implementation of a minimum cost perfect matching algorithm. Math. Program. Comput. 1(1), 43\u201367 (2009)","journal-title":"Math. Program. Comput."},{"issue":"1","key":"9289_CR15","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/s00493-006-0008-z","volume":"26","author":"C.H. Papadimitriou","year":"2006","unstructured":"Papadimitriou, C.H., Vempala, S.: On the approximability of the traveling salesman problem. Combinatorica 26(1), 101\u2013120 (2006)","journal-title":"Combinatorica"},{"key":"9289_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C.H. Papadimitriou","year":"1993","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18, 1\u201311 (1993)","journal-title":"Math. Oper. Res."},{"key":"9289_CR17","unstructured":"Reinelt, G.: TSPLIB library. University of Heidelberg, http:\/\/www.iwr.uni-heidelberg.de\/groups\/comopt\/software\/tsplib95\/"},{"key":"9289_CR18","unstructured":"TSP site. Concorde TSP solver, http:\/\/www.tsp.gatech.edu\/concorde\/"},{"issue":"2\u20133","key":"9289_CR19","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/S0166-218X(03)00451-7","volume":"136","author":"X. Tan","year":"2004","unstructured":"Tan, X.: Approximation algorithms for the watchman route and zookeeper\u2019s problems. Discrete Appl. Math. 136(2\u20133), 363\u2013376 (2004)","journal-title":"Discrete Appl. Math."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-010-9289-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-010-9289-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-010-9289-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,2]],"date-time":"2019-06-02T00:59:53Z","timestamp":1559437193000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-010-9289-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,8,18]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,10]]}},"alternative-id":["9289"],"URL":"https:\/\/doi.org\/10.1007\/s00224-010-9289-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,8,18]]}}}