{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:57:36Z","timestamp":1781305056845,"version":"3.54.1"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032286901","type":"print"},{"value":"9783032286918","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-28691-8_9","type":"book-chapter","created":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:35:57Z","timestamp":1781303757000},"page":"128-143","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Integrality Gap of\u00a0the\u00a0Traveling Salesman Problem is $$\\frac{4}{3}$$ if\u00a0the\u00a0LP Solution Has at\u00a0Most $$n + 6$$ Non-Zero Components"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-4669-4781","authenticated-orcid":false,"given":"Tullio","family":"Villa","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1621-2484","authenticated-orcid":false,"given":"Eleonora","family":"Vercesi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1577-5637","authenticated-orcid":false,"given":"Janos","family":"Barta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2948-9749","authenticated-orcid":false,"given":"Monaldo","family":"Mastrolilli","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,13]]},"reference":[{"key":"9_CR1","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1287\/moor.1080.0337","volume":"33","author":"G Benoit","year":"2008","unstructured":"Benoit, G., Boyd, S.: Finding the exact integrality gap for small traveling salesman problems. Math. Oper. Res. 33, 921\u2013931 (2008). https:\/\/doi.org\/10.1287\/moor.1080.0337","journal-title":"Math. Oper. Res."},{"issue":"4","key":"9_CR2","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. Disc. Optim. 8(4), 525\u2013539 (2011). https:\/\/doi.org\/10.1016\/j.disopt.2011.05.002","journal-title":"Disc. Optim."},{"key":"9_CR3","unstructured":"Boyd, S., Elliott-Magwood, P.: Structure of the extreme points of the subtour elimination polytope of the STSP. In: RIMS Kokyuroku Bessatsu, pp. 33\u201347 (2010). https:\/\/api.semanticscholar.org\/CorpusID:15182527"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Boyd, S., Pulleyblank, W.R.: Optimizing over the subtour polytope of the travelling salesman problem. Math. Program. 49, 163\u2013187 (1990). https:\/\/doi.org\/10.1007\/BF01588786","DOI":"10.1007\/BF01588786"},{"issue":"1","key":"9_CR5","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/s10107-019-01455-3","volume":"186","author":"S Boyd","year":"2021","unstructured":"Boyd, S., Seb\u0151, A.: The salesman\u2019s improved tours for fundamental classes. Math. Program. 186(1), 289\u2013307 (2021)","journal-title":"Math. Program."},{"key":"9_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. 6655, pp. 65\u201377. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-20807-2_6"},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Oper. Res. Forum 3 (1976)","DOI":"10.1007\/s43069-021-00101-z"},{"key":"9_CR8","doi-asserted-by":"publisher","unstructured":"Cornuejols, G., Fonlupt, J., Naddef, D.: The traveling salesman problem on a graph and some related integer polyhedra. Math. Program. 33, 1\u201327 (1985). https:\/\/doi.org\/10.1007\/BF01582008","DOI":"10.1007\/BF01582008"},{"issue":"4","key":"9_CR9","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. J. Oper. Res. Soc. Am. 2(4), 393\u2013410 (1954)","journal-title":"J. Oper. Res. Soc. Am."},{"issue":"1","key":"9_CR10","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/BF01585563","volume":"69","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X.: Worst-case comparison of valid inequalities for the TSP. Math. Program. 69(1), 335\u2013349 (1995)","journal-title":"Math. Program."},{"issue":"1","key":"9_CR11","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1007\/s10107-024-02065-4","volume":"206","author":"A Gupta","year":"2024","unstructured":"Gupta, A., Lee, E., Li, J., Mucha, M., Newman, H., Sarkar, S.: Matroid-based TSP rounding for half-integral solutions. Math. Program. 206(1), 541\u2013576 (2024)","journal-title":"Math. Program."},{"key":"9_CR12","unstructured":"Gurobi Optimization, LLC: Gurobi Optimizer Reference Manual (2024). https:\/\/www.gurobi.com"},{"issue":"8","key":"9_CR13","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1016\/j.orl.2014.08.009","volume":"42","author":"S Hougardy","year":"2014","unstructured":"Hougardy, S.: On the integrality ratio of the subtour LP for Euclidean TSP. Oper. Res. Lett. 42(8), 495\u2013499 (2014)","journal-title":"Oper. Res. Lett."},{"key":"9_CR14","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s12532-020-00184-5","volume":"13","author":"S Hougardy","year":"2021","unstructured":"Hougardy, S., Zhong, X.: Hard to solve instances of the Euclidean traveling salesman problem. Math. Program. Comput. 13, 51\u201374 (2021)","journal-title":"Math. Program. Comput."},{"key":"9_CR15","doi-asserted-by":"publisher","unstructured":"Jin, B., Klein, N., Williamson, D.P.: A 4\/3-approximation algorithm for half-integral cycle cut instances of the TSP. Math. Program. 209 (2025). https:\/\/doi.org\/10.1007\/s10107-025-02193-5","DOI":"10.1007\/s10107-025-02193-5"},{"key":"9_CR16","doi-asserted-by":"publisher","unstructured":"Karlin, A.R., Klein, N., Oveis\u00a0Gharan, S.: An improved approximation algorithm for TSP in the half integral case. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pp. 28\u201339. Association for Computing Machinery (2020). https:\/\/doi.org\/10.1145\/3357713.3384273","DOI":"10.1145\/3357713.3384273"},{"key":"9_CR17","doi-asserted-by":"publisher","unstructured":"Karlin, A.R., Klein, N., Oveis\u00a0Gharan, S.: A (slightly) improved approximation algorithm for metric TSP. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pp. 32\u201345. Association for Computing Machinery (2021). https:\/\/doi.org\/10.1145\/3406325.3451009","DOI":"10.1145\/3406325.3451009"},{"key":"9_CR18","doi-asserted-by":"publisher","unstructured":"Karlin, A.R., Klein, N., Oveis\u00a0Gharan, S.: A (slightly) improved bound on the integrality gap of the subtour LP for TSP. In: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 832\u2013843. IEEE Computer Society (2022). https:\/\/doi.org\/10.1109\/FOCS54457.2022.00084","DOI":"10.1109\/FOCS54457.2022.00084"},{"key":"9_CR19","unstructured":"Klein, N., Taziki, M.: Dual charging for half-integral TSP (2025). arXiv preprint arXiv:2507.17999"},{"key":"9_CR20","doi-asserted-by":"publisher","unstructured":"M\u00f6mke, T., Svensson, O.: Removing and adding edges for the traveling salesman problem. J. ACM 63(1), 2:1\u20132:28 (2016). https:\/\/doi.org\/10.1145\/2739008","DOI":"10.1145\/2739008"},{"issue":"2","key":"9_CR21","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1287\/moor.2013.0608","volume":"39","author":"F Schalekamp","year":"2014","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)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"9_CR22","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/s12532-023-00235-7","volume":"15","author":"E Vercesi","year":"2023","unstructured":"Vercesi, E., Gualandi, S., Mastrolilli, M., Gambardella, L.M.: On the generation of metric TSP instances with a large integrality gap by branch-and-cut. Math. Program. Comput. 15(2), 389\u2013416 (2023). https:\/\/doi.org\/10.1007\/s12532-023-00235-7","journal-title":"Math. Program. Comput."},{"key":"9_CR23","unstructured":"Villa, T., Vercesi, E., Barta, J., Mastrolilli, M.: The integrality gap of the traveling salesman problem is 4\/3 if the LP solution has at most n+6 non-zero components (2025). https:\/\/arxiv.org\/abs\/2507.07003"},{"key":"9_CR24","doi-asserted-by":"publisher","unstructured":"Wolsey, L.A.: Heuristic analysis, linear programming and branch and bound. In: Rayward-Smith, V.J. (ed.) Combinatorial Optimization II, pp. 121\u2013134. Springer, Heidelberg (1980). https:\/\/doi.org\/10.1007\/BFb0120913","DOI":"10.1007\/BFb0120913"},{"key":"9_CR25","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.dam.2024.12.029","volume":"365","author":"X Zhong","year":"2025","unstructured":"Zhong, X.: Lower bounds on the integrality ratio of the subtour LP for the traveling salesman problem. Disc. Appl. Math. 365, 109\u2013129 (2025)","journal-title":"Disc. Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-28691-8_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:36:00Z","timestamp":1781303760000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-28691-8_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032286901","9783032286918"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-28691-8_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"13 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Padua","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/events.math.unipd.it\/ipco2026\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}