{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T07:55:10Z","timestamp":1777362910830,"version":"3.51.4"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T00:00:00Z","timestamp":1761523200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T00:00:00Z","timestamp":1761523200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["CCF-2007009"],"award-info":[{"award-number":["CCF-2007009"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","award":["PGSD3-532673-2019"],"award-info":[{"award-number":["PGSD3-532673-2019"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1926686"],"award-info":[{"award-number":["DMS-1926686"]}],"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-1762114"],"award-info":[{"award-number":["DGE-1762114"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF- 1813135"],"award-info":[{"award-number":["CCF- 1813135"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    One of the most famous conjectures in combinatorial optimization is the four-thirds conjecture, which states that the integrality gap of the Subtour LP relaxation of the TSP is equal to\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\frac{4}{3}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mfrac>\n                            <mml:mn>4<\/mml:mn>\n                            <mml:mn>3<\/mml:mn>\n                          <\/mml:mfrac>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . For 40 years, the best known upper bound was 1.5, due to Wolsey [1]. Recently, Karlin, Klein, and Oveis Gharan [2] showed that the max entropy algorithm for the TSP gives an improved bound of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$1.5 - 10^{-36}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mn>1.5<\/mml:mn>\n                            <mml:mo>-<\/mml:mo>\n                            <mml:msup>\n                              <mml:mn>10<\/mml:mn>\n                              <mml:mrow>\n                                <mml:mo>-<\/mml:mo>\n                                <mml:mn>36<\/mml:mn>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . In this paper, we show that the approximation ratio of the max entropy algorithm is at least 1.375, even for graph TSP. Thus the max entropy algorithm does not appear to be the algorithm that will ultimately resolve the four-thirds conjecture in the affirmative, should that be possible.\n                  <\/jats:p>","DOI":"10.1007\/s10107-025-02289-y","type":"journal-article","created":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T11:41:14Z","timestamp":1761565274000},"page":"425-447","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A lower bound for the max entropy algorithm for TSP"],"prefix":"10.1007","volume":"216","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6362-2048","authenticated-orcid":false,"given":"Billy","family":"Jin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nathan","family":"Klein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David P.","family":"Williamson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,10,27]]},"reference":[{"key":"2289_CR1","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":"2289_CR2","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, CA, USA (2022). https:\/\/doi.org\/10.1109\/FOCS54457.2022.00084","DOI":"10.1109\/FOCS54457.2022.00084"},{"key":"2289_CR3","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":"2289_CR4","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":"2289_CR5","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/s00493-014-2960-3","volume":"34","author":"A Seb\u0151","year":"2014","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 34, 597\u2013629 (2014)","journal-title":"Combinatorica"},{"issue":"4","key":"2289_CR6","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. J. Operations Research Soc. America 2(4), 393\u2013410 (1954). (Accessed 2023-02-28)","journal-title":"J. Operations Research Soc. America"},{"key":"2289_CR7","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":"2289_CR8","doi-asserted-by":"publisher","first-page":"1043","DOI":"10.1287\/opre.2017.1603","volume":"65","author":"A Asadpour","year":"2017","unstructured":"Asadpour, A., Goemans, M.X., Ma\u0327dry, A., Oveis Gharan, S., Saberi, A.: An $${O}(\\log n\/\\log \\log n)$$-approximation algorithm for the asymmetric traveling salesman problem. Operations Research 65, 1043\u20131061 (2017)","journal-title":"Operations Research"},{"key":"2289_CR9","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 the Foundations of Computer Science, pp. 550\u2013559 (2011)","DOI":"10.1109\/FOCS.2011.80"},{"issue":"6","key":"2289_CR10","doi-asserted-by":"publisher","first-page":"2543","DOI":"10.1287\/opre.2022.2338","volume":"72","author":"AR Karlin","year":"2024","unstructured":"Karlin, A.R., Klein, N., Oveis Gharan, S.: A (slightly) improved approximation algorithm for metric tsp. Oper. Res. 72(6), 2543\u20132594 (2024). https:\/\/doi.org\/10.1287\/opre.2022.2338","journal-title":"Oper. Res."},{"key":"2289_CR11","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."},{"key":"2289_CR12","doi-asserted-by":"publisher","unstructured":"Gurvits, L., Klein, N., Leake, J.: From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP. In: Bringmann, K., Grohe, M., Puppis, G., Svensson, O. (eds.) 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), vol. 297, pp. 79\u201317920. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2024). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2024.79","DOI":"10.4230\/LIPIcs.ICALP.2024.79"},{"key":"2289_CR13","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":"2289_CR14","first-page":"33","volume":"B23","author":"S Boyd","year":"2010","unstructured":"Boyd, S., Elliott-Magwood, P.: Structure of extreme points of the subtour elimination polytope of the STSP. RIMS K\u00f4ky\u00fbroko Besstsu B23, 33\u201347 (2010)","journal-title":"RIMS K\u00f4ky\u00fbroko Besstsu"},{"key":"2289_CR15","doi-asserted-by":"publisher","first-page":"1109","DOI":"10.1007\/s00453-017-0293-5","volume":"78","author":"K Genova","year":"2017","unstructured":"Genova, K., Williamson, D.P.: An experimental evaluation of the best-of-many Christofides\u2019 algorithm for the traveling salesman problem. Algorithmica 78, 1109\u20131130 (2017)","journal-title":"Algorithmica"},{"key":"2289_CR16","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."},{"key":"2289_CR17","unstructured":"Karlin, A.R., Klein, N., Oveis Gharan, S.: An improved approximation algorithm for TSP in the half integral case. In: Proceedings of the 52nd Annual ACM Symposium on the Theory of Computing, pp. 28\u201339 (2020)"},{"key":"2289_CR18","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/BF01588786","volume":"49","author":"SC Boyd","year":"1991","unstructured":"Boyd, S.C., Pulleyblank, W.R.: Optimizing over the subtour polytope of the travelling salesman problem. Math. Program. 49, 163\u2013187 (1991)","journal-title":"Math. Program."},{"key":"2289_CR19","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0196-6774(84)90029-4","volume":"5","author":"CH Papadimitriou","year":"1984","unstructured":"Papadimitriou, C.H., Vazirani, U.V.: On two geometric problems related to the travelling salesman problem. J. Algorithms 5, 231\u2013246 (1984)","journal-title":"J. Algorithms"},{"key":"2289_CR20","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":"2289_CR21","doi-asserted-by":"crossref","unstructured":"Jin, B., Klein, N., Williamson, D.P.: A 4\/3-approximation algorithm for half-integral cycle cut instances of the TSP. In: Del\u00a0Pia, A., Kaibel, V. (eds.) Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, pp. 217\u2013230. Springer, Berlin, Germany (2023)","DOI":"10.1007\/978-3-031-32726-1_16"},{"key":"2289_CR22","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1137\/0206041","volume":"6","author":"DJ Rosenkrantz","year":"1977","unstructured":"Rosenkrantz, D.J., Stearns, R.E., Lewis, P.M., II.: An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput. 6, 563\u2013581 (1977)","journal-title":"SIAM J. Comput."},{"key":"2289_CR23","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/BF01588956","volume":"14","author":"G Cornuejols","year":"1978","unstructured":"Cornuejols, G., Nemhauser, G.L.: Tight bounds for christofides\u2019 traveling salesman heuristic. Math. Program. 14, 116\u2013121 (1978)","journal-title":"Math. Program."},{"key":"2289_CR24","doi-asserted-by":"publisher","first-page":"1998","DOI":"10.1137\/S0097539793251244","volume":"28","author":"B Chandra","year":"2006","unstructured":"Chandra, B., Karloff, H., Tovey, C.: New results on the old $$k$$-OPT algorithm for the traveling salesman problem. SIAM J. Comput. 28, 1998\u20132029 (2006)","journal-title":"SIAM J. Comput."},{"key":"2289_CR25","unstructured":"Zhong, X.: On the approximation ratio of $$k$$-Opt and Lin-Kernighan algorithm. Preprint, https:\/\/arxiv.org\/pdf\/1909.12755.pdf"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02289-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-025-02289-y","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02289-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T07:11:06Z","timestamp":1777360266000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-025-02289-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,27]]},"references-count":25,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["2289"],"URL":"https:\/\/doi.org\/10.1007\/s10107-025-02289-y","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,27]]},"assertion":[{"value":"31 July 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 September 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 October 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}