{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T02:05:00Z","timestamp":1725674700859},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642293436"},{"type":"electronic","value":"9783642293443"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-29344-3_51","type":"book-chapter","created":{"date-parts":[[2012,4,10]],"date-time":"2012-04-10T10:19:29Z","timestamp":1334053169000},"page":"606-617","source":"Crossref","is-referenced-by-count":3,"title":["On the Integrality Gap of the Subtour LP for the 1,2-TSP"],"prefix":"10.1007","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","reference":[{"key":"51_CR1","unstructured":"Aggarwal, N., Garg, N., Gupta, S.: A 4\/3-approximation for TSP on cubic 3-edge-connected graphs (2011), \n                  \n                    http:\/\/arxiv.org\/abs\/1101.5586"},{"key":"51_CR2","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1287\/mnsc.12.3.253","volume":"12","author":"M.L. Balinski","year":"1965","unstructured":"Balinski, M.L.: Integer programming: Methods, uses, computation. Management Science\u00a012, 253\u2013313 (1965)","journal-title":"Management Science"},{"key":"51_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":"51_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1007\/11537311_44","volume-title":"Fundamentals of Computation Theory","author":"M. Bl\u00e4ser","year":"2005","unstructured":"Bl\u00e4ser, M., Shankar Ram, L.: An Improved Approximation Algorithm for TSP with Distances One and Two. In: Li\u015bkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol.\u00a03623, pp. 504\u2013515. Springer, Heidelberg (2005)"},{"issue":"4","key":"51_CR5","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1016\/j.disopt.2011.05.002","volume":"8","author":"S. Boyd","year":"2011","unstructured":"Boyd, S., Carr, R.: Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices. Discrete Optimization\u00a08(4), 525\u2013539 (2011), prior version, \n                  \n                    http:\/\/www.site.uottawa.ca\/~sylvia\/recentpapers\/halftri.pdf\n                  \n                  \n                 (accessed June 27, 2011)","journal-title":"Discrete Optimization"},{"key":"51_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-3-642-20807-2_6","volume-title":"Integer Programming and Combinatoral Optimization","author":"S. Boyd","year":"2011","unstructured":"Boyd, S., Sitters, R., van der Ster, S., Stougie, L.: TSP on Cubic and Subcubic Graphs. In: G\u00fcnl\u00fck, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol.\u00a06655, pp. 65\u201377. Springer, Heidelberg (2011)"},{"key":"51_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":"51_CR8","unstructured":"IBM ILOG CPLEX 12.1 (2009)"},{"key":"51_CR9","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1287\/opre.2.4.393","volume":"2","author":"G. Dantzig","year":"1954","unstructured":"Dantzig, G., Fulkerson, R., Johnson, S.: Solution of a large-scale traveling-salesman problem. Operations Research\u00a02, 393\u2013410 (1954)","journal-title":"Operations Research"},{"key":"51_CR10","first-page":"335","volume":"69","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X.: Worst-case comparison of valid inequalities for the TSP. Mathematical Programming\u00a069, 335\u2013349 (1995)","journal-title":"Mathematical Programming"},{"key":"51_CR11","first-page":"45","volume":"30","author":"B.D. McKay","year":"1981","unstructured":"McKay, B.D.: Practical graph isomorphism. Congressus Numerantium\u00a030, 45\u201397 (1981)","journal-title":"Congressus Numerantium"},{"key":"51_CR12","doi-asserted-by":"crossref","unstructured":"M\u00f6mke, T., Svensson, O.: Approximating graphic TSP by matchings. In: Proceedings of the 52th Annual Symposium on Foundations of Computer Science (2011)","DOI":"10.1109\/FOCS.2011.56"},{"key":"51_CR13","doi-asserted-by":"crossref","unstructured":"Mucha, M.: 13\/9-approximation for graphic TSP. In: 29th International Symposium on Theoretical Aspects of Computer Science (2012)","DOI":"10.1007\/s00224-012-9439-7"},{"key":"51_CR14","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 52th Annual Symposium on Foundations of Computer Science (2011)","DOI":"10.1109\/FOCS.2011.80"},{"key":"51_CR15","doi-asserted-by":"publisher","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. Mathematics of Operations Research\u00a018, 1\u201311 (1993)","journal-title":"Mathematics of Operations Research"},{"key":"51_CR16","doi-asserted-by":"crossref","unstructured":"Schalekamp, F., Williamson, D.P., van Zuylen, A.: A proof of the Boyd-Carr conjecture. In: Proceedings of the 23nd ACM-SIAM Symposium on Discrete Algorithms (2012)","DOI":"10.1137\/1.9781611973099.117"},{"key":"51_CR17","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0020-0190(90)90028-V","volume":"35","author":"D.B. Shmoys","year":"1990","unstructured":"Shmoys, D.B., Williamson, D.P.: Analyzing the Held-Karp TSP bound: A monotonicity property with application. Information Processing Letters\u00a035, 281\u2013285 (1990)","journal-title":"Information Processing Letters"},{"key":"51_CR18","unstructured":"Williamson, D.P.: Analysis of the Held-Karp Heuristic for the Traveling Salesman Problem. Master\u2019s thesis. MIT, Cambridge, MA (June 1990), also appears as Tech. Report MIT\/LCS\/TR-479"},{"key":"51_CR19","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BFb0120913","volume":"13","author":"L.A. Wolsey","year":"1980","unstructured":"Wolsey, L.A.: Heuristic analysis, linear programming and branch and bound. Mathematical Programming Study\u00a013, 121\u2013134 (1980)","journal-title":"Mathematical Programming Study"}],"container-title":["Lecture Notes in Computer Science","LATIN 2012: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-29344-3_51","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T23:55:00Z","timestamp":1556668500000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-29344-3_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642293436","9783642293443"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-29344-3_51","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}