{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T16:17:43Z","timestamp":1784305063983,"version":"3.55.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2025,2,17]],"date-time":"2025-02-17T00:00:00Z","timestamp":1739750400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,2,17]],"date-time":"2025-02-17T00:00:00Z","timestamp":1739750400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-2007009"],"award-info":[{"award-number":["CCF-2007009"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-155209"],"award-info":[{"award-number":["CCF-155209"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1813135"],"award-info":[{"award-number":["CCF-1813135"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["PGSD3-532673-2019"],"award-info":[{"award-number":["PGSD3-532673-2019"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000082","name":"Division of Graduate Education","doi-asserted-by":"publisher","award":["DGE-1650441"],"award-info":[{"award-number":["DGE-1650441"]}],"id":[{"id":"10.13039\/100000082","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,3]]},"DOI":"10.1007\/s10107-025-02193-5","type":"journal-article","created":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T01:48:43Z","timestamp":1739843323000},"page":"511-538","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A $$\\frac{4}{3}$$-approximation algorithm for half-integral cycle cut instances of the TSP"],"prefix":"10.1007","volume":"210","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6362-2048","authenticated-orcid":false,"given":"Billy","family":"Jin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nathan","family":"Klein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David P.","family":"Williamson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,2,17]]},"reference":[{"key":"2193_CR1","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, 335\u2013349 (1995)","journal-title":"Math. Program."},{"key":"2193_CR2","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)","journal-title":"Math. Oper. Res."},{"key":"2193_CR3","doi-asserted-by":"publisher","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"},{"key":"2193_CR4","doi-asserted-by":"publisher","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-Karp TSP bound: a monotonicity property with application. Inf. Process. Lett. 35, 281\u2013285 (1990)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"2193_CR5","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."},{"key":"2193_CR6","doi-asserted-by":"crossref","unstructured":"Karlin, A.R., Klein, N., Oveis Gharan, S.: An improved approximation algorithm for TSP in the half integral case. In: Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G., Chuzhoy, J. (eds.) Proceedings of the 52nd Annual ACM Symposium on the Theory of Computing, pp. 28\u201339. ACM, New York (2020)","DOI":"10.1145\/3357713.3384273"},{"key":"2193_CR7","doi-asserted-by":"crossref","unstructured":"Gupta, A., Lee, E., Li, J., Mucha, M., Newman, H., Sarkar, S.: Matroid-based TSP rounding for half-integral solutions. In: Aardal, K., Sanit\u00e0, L. (eds.) Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, pp. 305\u2013318 (2022). See also arXiv:2111.09290pdf","DOI":"10.1007\/978-3-031-06901-7_23"},{"key":"2193_CR8","doi-asserted-by":"publisher","unstructured":"Karlin, A., Klein, N., Oveis Gharan, 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, Los Alamitos (2022). https:\/\/doi.org\/10.1109\/FOCS54457.2022.00084. https:\/\/doi.ieeecomputersociety.org\/10.1109\/FOCS54457.2022.00084","DOI":"10.1109\/FOCS54457.2022.00084"},{"key":"2193_CR9","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":"2193_CR10","first-page":"76","volume":"17","author":"A Serdyukov","year":"1978","unstructured":"Serdyukov, A.: On some extremal walks in graphs. Upravlyaemye Sistemy 17, 76\u201379 (1978)","journal-title":"Upravlyaemye Sistemy"},{"key":"2193_CR11","doi-asserted-by":"crossref","unstructured":"Seb\u0151, A., Vygen, J.: Shorter tours by nicer ears: 7\/5-approximation for the graph-TSP, 3\/2 for the path version, and 4\/3 for two-edge-connected subgraphs. Combinatorica, 1\u201334 (2014)","DOI":"10.1007\/s00493-014-2960-3"},{"key":"2193_CR12","doi-asserted-by":"crossref","unstructured":"Karlin, A.R., Klein, N., Oveis Gharan, S.: A (slightly) improved approximation algorithm for metric TSP. In: Proceedings of the 53rd Annual ACM Symposium on the Theory of Computing, pp. 32\u201345. ACM, New York (2021)","DOI":"10.1145\/3406325.3451009"},{"key":"2193_CR13","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":"2193_CR14","doi-asserted-by":"publisher","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","volume":"18","author":"M Held","year":"1971","unstructured":"Held, M., Karp, R.M.: The traveling-salesman problem and minimum spanning trees. Oper. Res. 18, 1138\u20131162 (1971)","journal-title":"Oper. Res."},{"key":"2193_CR15","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, 289\u2013307 (2021)","journal-title":"Math. Program."},{"issue":"1","key":"2193_CR16","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(1), 51\u201374 (2021). https:\/\/doi.org\/10.1007\/s12532-020-00184-5","journal-title":"Math. Program. Comput."},{"key":"2193_CR17","unstructured":"Xianghui, Z.: Approximation algorithms for the traveling salesman problem. PhD thesis, Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn (2021). https:\/\/hdl.handle.net\/20.500.11811\/9076"},{"key":"2193_CR18","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/2739008","volume":"63","author":"T M\u00f6mke","year":"2016","unstructured":"M\u00f6mke, T., Svensson, O.: Removing and adding edges for the traveling salesman problem. J. ACM 63, 2 (2016)","journal-title":"J. ACM"},{"key":"2193_CR19","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 Optim. 8, 525\u2013539 (2011)","journal-title":"Discrete Optim."},{"key":"2193_CR20","unstructured":"Haddadan, A., Newman, A.: Towards improving Christofides algorithm for half-integer TSP. In: Bender, M.A., Svensson, O., Herman, G. (eds.) 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), vol. 144, pp. 56\u201315612. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2019). See also arXiv:1907.02120v3.pdf"},{"key":"2193_CR21","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1007\/3-540-69346-7_9","volume-title":"Integer Programming and Combinatorial Optimization","author":"R Carr","year":"1998","unstructured":"Carr, R., Ravi, R.: A new bound for the 2-edge connected subgraph problem. In: Bixby, R.E., Boyd, E.A., R\u00edos-Mercado, R.Z. (eds.) Integer Programming and Combinatorial Optimization, pp. 112\u2013125. Springer, Berlin (1998)"},{"key":"2193_CR22","unstructured":"Fleiner, T., Frank, A.: A quick proof for the cactus representation of mincuts. Technical Report QP-2009-03, Egerv\u00e1ry Research Group, Budapest (2009). www.cs.elte.hu\/egres"},{"key":"2193_CR23","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"2012","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (2012)"},{"key":"2193_CR24","doi-asserted-by":"publisher","DOI":"10.1017\/9781316888568","volume-title":"Network Flow Algorithms","author":"DP Williamson","year":"2019","unstructured":"Williamson, D.P.: Network Flow Algorithms. Cambridge University Press, New York (2019)"},{"key":"2193_CR25","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/0-306-48213-4_9","volume-title":"The Traveling Salesman Problem and Its Variations","author":"DS Johnson","year":"2007","unstructured":"Johnson, D.S., McGeoch, L.A.: Experimental analysis of heuristics for the STSP. In: Gutin, G., Punnen, A.P. (eds.) The Traveling Salesman Problem and Its Variations, pp. 369\u2013444. Springer, New York (2007)"},{"key":"2193_CR26","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1006\/jagm.1999.1039","volume":"33","author":"L Fleischer","year":"1999","unstructured":"Fleischer, L.: Building chain and cactus representations of all minimum cuts from Hao-Orlin in the same asymptotic run time. J. Algorithms 33, 51\u201372 (1999)","journal-title":"J. Algorithms"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02193-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-025-02193-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02193-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T16:05:00Z","timestamp":1740758700000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-025-02193-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,17]]},"references-count":26,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["2193"],"URL":"https:\/\/doi.org\/10.1007\/s10107-025-02193-5","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,17]]},"assertion":[{"value":"10 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 October 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 February 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have none to declare.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"No humans or animals were harmed in the making of this paper.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}}]}}