{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,8]],"date-time":"2026-03-08T07:02:18Z","timestamp":1772953338419,"version":"3.50.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,11,12]],"date-time":"2014-11-12T00:00:00Z","timestamp":1415750400000},"content-version":"tdm","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":[[2015,4]]},"DOI":"10.1007\/s10107-014-0835-4","type":"journal-article","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T16:33:39Z","timestamp":1415982819000},"page":"131-151","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On the integrality gap of the subtour LP for the 1,2-TSP"],"prefix":"10.1007","volume":"150","author":[{"given":"Jiawei","family":"Qian","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frans","family":"Schalekamp","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David P.","family":"Williamson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anke","family":"van Zuylen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,11,12]]},"reference":[{"key":"835_CR1","unstructured":"Aggarwal, N., Garg, N., Gupta, S.: A 4\/3-approximation for TSP on cubic 3-edge-connected graphs. CoRR abs\/1101.5586 (2011)"},{"key":"835_CR2","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1287\/mnsc.12.3.253","volume":"12","author":"ML Balinski","year":"1965","unstructured":"Balinski, M.L.: Integer programming: methods, uses, computation. Manag. Sci. 12, 253\u2013313 (1965)","journal-title":"Manag. Sci."},{"key":"835_CR3","doi-asserted-by":"crossref","unstructured":"Berman, P., Karpinski, M.: 8\/7-approximation algorithm for (1,2)-TSP. In: Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, pp. 641\u2013648 (2006)","DOI":"10.1145\/1109557.1109627"},{"key":"835_CR4","doi-asserted-by":"crossref","unstructured":"Bl\u00e4ser, M., Shankar Ram, L.: An improved approximation algorithm for TSP with distances one and two. In: Liskiewicz, M., Reischuk, R. (eds.) Fundamentals of Computation Theory, 15th International Symposium, FCT 2005, Lecture Notes in Computer Science, vol. 3623, pp. 504\u2013515. Springer (2005)","DOI":"10.1007\/11537311_44"},{"key":"835_CR5","doi-asserted-by":"crossref","unstructured":"Boyd, S., Carr, R.: Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices. Discrete Optim. 8, 525\u2013539 (2011). Prior version available at http:\/\/www.site.uottawa.ca\/sylvia\/recentpapers\/halftri.pdf . Accessed 27 June 2011","DOI":"10.1016\/j.disopt.2011.05.002"},{"key":"835_CR6","doi-asserted-by":"crossref","unstructured":"Boyd, S., Sitters, R., van der Ster, S., Stougie, L.: The traveling salesman problem on cubic and subcubic graphs. Math. Program. 144(1\u20132), 227\u2013245 (2014). A preliminary version appeared in IPCO 2011","DOI":"10.1007\/s10107-012-0620-1"},{"key":"835_CR7","unstructured":"Christofides, N.: Worst case analysis of a new heuristic for the traveling salesman problem. Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA (1976)"},{"key":"835_CR8","first-page":"393","volume":"2","author":"G Dantzig","year":"1954","unstructured":"Dantzig, G., Fulkerson, R., Johnson, S.: Solution of a large-scale traveling-salesman problem. Oper. Res. 2, 393\u2013410 (1954)","journal-title":"Oper. Res."},{"key":"835_CR9","unstructured":"Gamarnik, D., Lewenstein, M., Sviridenko, M.: An improved upper bound for the TSP in cubic 3-edge-connected graphs. Oper. Res. Lett. 33(5), 467\u2013474 (2005)"},{"key":"835_CR10","first-page":"335","volume":"69","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X.: Worst-case comparison of valid inequalities for the TSP. Math. Program. 69, 335\u2013349 (1995)","journal-title":"Math. Program."},{"key":"835_CR11","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF01580607","volume":"60","author":"MX Goemans","year":"1990","unstructured":"Goemans, M.X., Bertsimas, D.J.: Survivable networks, linear programming relaxations, and the parsimonious property. Math. Program. 60, 145\u2013166 (1990)","journal-title":"Math. Program."},{"key":"835_CR12","unstructured":"IBM ILOG CPLEX 12.1 (2009)"},{"key":"835_CR13","first-page":"45","volume":"30","author":"BD McKay","year":"1981","unstructured":"McKay, B.D.: Practical graph isomorphism. Congr. Numerantium 30, 45\u201397 (1981)","journal-title":"Congr. Numerantium"},{"key":"835_CR14","unstructured":"Mnich, M., M\u00f6mke, T.: Improved integrality gap upper bounds for TSP with distances one and two. CoRR abs\/1312.2502 (2013)"},{"key":"835_CR15","doi-asserted-by":"crossref","unstructured":"M\u00f6mke, T., Svensson, O.: Approximating graphic TSP by matchings. In: Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, pp. 560\u2013569 (2011)","DOI":"10.1109\/FOCS.2011.56"},{"key":"835_CR16","doi-asserted-by":"crossref","unstructured":"Mucha, M.: $$\\frac{13}{9}$$ 13 9 -approximation for graphic TSP. Theory Comput. Syst., 1\u201318 (2012). A preliminary version appeared in STACS 2012","DOI":"10.1007\/s00224-012-9439-7"},{"key":"835_CR17","doi-asserted-by":"crossref","unstructured":"Oveis Gharan, S., Saberi, A., Singh, M.: A randomized rounding approach to the traveling salesman problem. In: Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, pp. 550\u2013559 (2011)","DOI":"10.1109\/FOCS.2011.80"},{"key":"835_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"CH 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":"835_CR19","doi-asserted-by":"crossref","unstructured":"Qian, J., Schalekamp, F., Williamson, D.P., van Zuylen, A.: On the integrality gap of the subtour LP for the 1,2-TSP. In: LATIN 2012: Theoretical Informatics, 10th Latin American Symposium, Lecture Notes in Computer Science, vol. 7256, pp. 606\u2013617 (2012)","DOI":"10.1007\/978-3-642-29344-3_51"},{"key":"835_CR20","doi-asserted-by":"crossref","unstructured":"Schalekamp, F., Williamson, D.P., van Zuylen, A.: 2-matchings, the traveling salesman problem, and the subtour LP: A proof of the Boyd-Carr conjecture. Math. Oper. Res. 39(2), 403\u2013417 (2014). A preliminary version appeared in SODA 2012","DOI":"10.1287\/moor.2013.0608"},{"key":"835_CR21","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)"},{"key":"835_CR22","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0020-0190(90)90028-V","volume":"35","author":"DB Shmoys","year":"1990","unstructured":"Shmoys, D.B., Williamson, D.P.: Analyzing the Held\u2013Karp TSP bound: a monotonicity property with application. Inf. Process. Lett. 35, 281\u2013285 (1990)","journal-title":"Inf. Process. Lett."},{"key":"835_CR23","unstructured":"Williamson, D.P.: Analysis of the Held\u2013Karp heuristic for the traveling salesman problem. Master\u2019s thesis, MIT, Cambridge, MA (1990). Also appears as Tech Report MIT\/LCS\/TR-479"},{"key":"835_CR24","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BFb0120913","volume":"13","author":"LA Wolsey","year":"1980","unstructured":"Wolsey, L.A.: Heuristic analysis, linear programming and branch and bound. Math. Program. Study 13, 121\u2013134 (1980)","journal-title":"Math. Program. Study"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-014-0835-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-014-0835-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-014-0835-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,17]],"date-time":"2019-08-17T10:44:38Z","timestamp":1566038678000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-014-0835-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,12]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,4]]}},"alternative-id":["835"],"URL":"https:\/\/doi.org\/10.1007\/s10107-014-0835-4","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11,12]]}}}