{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:43:43Z","timestamp":1787341423408,"version":"build-2736575974"},"reference-count":33,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1552831"],"award-info":[{"award-number":["CCF-1552831"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DGE-1650441"],"award-info":[{"award-number":["DGE-1650441"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We study a semidefinite programming relaxation of the traveling salesman problem introduced by de Klerk, Pasechnik, and Sotirov [ SIAM J. Optim., 19 (2008), pp. 1559--1573] and show that their relaxation has an unbounded integrality gap. In particular, we give a family of instances such that the gap increases linearly with $n$. To obtain this result, we search for feasible solutions within a highly structured class of matrices; the problem of finding such solutions reduces to finding feasible solutions for a related linear program, which we do analytically. The solutions we find imply the unbounded integrality gap. Further, these solutions imply several corollaries that help us better understand the semidefinite program and its relationship to other TSP relaxations. Using the same technique, we show that a more general semidefinite program introduced by de Klerk, de Oliveira Filho, and Pasechnik [ Handbook on Semidefinite, Conic and Polynomial Optimization, Springer, New York, 2012, pp. 171--199.] for the $k$-cycle cover problem also has an unbounded integrality gap.<\/jats:p>","DOI":"10.1137\/17m1154722","type":"journal-article","created":{"date-parts":[[2018,7,26]],"date-time":"2018-07-26T13:04:55Z","timestamp":1532610295000},"page":"2073-2096","source":"Crossref","is-referenced-by-count":5,"title":["The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem"],"prefix":"10.1137","volume":"28","author":[{"given":"Samuel C.","family":"Gutekunst","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David P.","family":"Williamson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,7,26]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/040605849"},{"key":"atypb3","first-page":"139","author":"Chlamtac E.","year":"2012","journal-title":"New York"},{"key":"atypb4","unstructured":"N. Christofides,\n                      Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem\n                      , Technical report 388, Carnegie-Mellon University, Pittsburgh, PA, 1976."},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"D. Cvetkovic\u0301, M. C\u030cangalovic\u0301, and V. Kovac\u030cevic\u0301-Vujc\u030cic\u0301,\n                      Semidefinite programming methods for the symmetric traveling salesman problem\n                      , in IPCO 1999: Integer Programming and Combinatorial Optimization, Lecture Notes in Comput. Sci. 1610, G. Cornue\u0301jols, R. E. Burkard, and G. J. Woeginger, eds., Springer, Berlin, 1999, pp. 126-136.","DOI":"10.1007\/3-540-48777-8_10"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2.4.393"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"E. de Klerk, F. de Oliveira Filho, and D. Pasechnik,\n                      Relaxations of combinatorial problems via association schemes\n                      , in Handbook on Semidefinite, Conic and Polynomial Optimization, Internat. Ser. Oper. Res. Management Sci. 166, M. F. Anjos and J. B. Lasserre, eds., Springer, New York, 2012, pp. 171-199.","DOI":"10.1007\/978-1-4614-0769-0_7"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.01.026"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/070711141"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-010-0411-5"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/14096712X"},{"key":"atypb12","first-page":"550","author":"Gharan S. O.","year":"2011","journal-title":"NJ"},{"key":"atypb13","first-page":"343","author":"Goemans M.","year":"2000","journal-title":"New York"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/s006070050038"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1561\/0100000006"},{"key":"atypb17","first-page":"251","author":"Gro\u0308tschel M.","year":"1985","journal-title":"New York"},{"key":"atypb18","unstructured":"S. C. Gutekunst and D. P. Williamson,\n                      The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem\n                      , preprint,https:\/\/arxiv.org\/abs\/1710.08455, 2017."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1287\/opre.18.6.1138"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"R. A. Horn and C. R. Johnson,\n                      Topics in Matrix Analysis\n                      , Cambridge University Press, Cambridge, 1991.","DOI":"10.1017\/CBO9780511840371"},{"key":"atypb21","unstructured":"A. Jeffrey and H.H. Dai,\n                      Handbook of Mathematical Formulas and Integrals\n                      , 4th ed., Academic Press, New York, 2008."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.06.003"},{"key":"atypb23","first-page":"293","author":"Lasserre J. B.","year":"2001","journal-title":"Berlin"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/0801013"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796309764"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1145\/2739008"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9439-7"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-2960-3"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90028-V"},{"key":"atypb31","first-page":"29","author":"Spielman D. A.","year":"2007","journal-title":"NJ"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"D. P. Williamson and D. B. Shmoys,\n                      The Design of Approximation Algorithms\n                      , Cambridge University Press, New York, 2011.","DOI":"10.1017\/CBO9780511921735"},{"key":"atypb33","first-page":"121","author":"Wolsey L. A.","year":"1980","journal-title":"Berlin"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1154722","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:18:50Z","timestamp":1787339930000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1154722"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1154722"],"URL":"https:\/\/doi.org\/10.1137\/17m1154722","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}