{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T18:49:03Z","timestamp":1776106143752,"version":"3.50.1"},"reference-count":44,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["INFORMS Journal on Computing"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:p>Let [Formula: see text] be n independent and uniformly distributed random points in a compact region [Formula: see text] of area 1. Let [Formula: see text] denote the length of the optimal Euclidean traveling salesman tour that traverses all these points. The classical Beardwood-Halton-Hammersley theorem proves the existence of a universal constant [Formula: see text] such [Formula: see text] almost surely, which satisfies [Formula: see text]. This paper presents a computer-aided proof using numerical quadrature and decision trees that [Formula: see text]. Although our improvement is still somewhat small, our approach has the advantage that it is primarily limited by computer hardware and is thus amenable to further improvements over time.<\/jats:p>\n                  <jats:p>History: Accepted by Russell Bent, Area Editor for Network Optimization: Algorithms &amp; Applications.<\/jats:p>\n                  <jats:p>Funding: This work was supported by the Office of Naval Research [Grants AWD-00008450, N00014-20-S-B001, and N00014-21-1-2208], the California Department of Transportation, and the U.S. Department of Transportation [Grant 69A3551747114].<\/jats:p>\n                  <jats:p>Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https:\/\/pubsonline.informs.org\/doi\/suppl\/10.1287\/ijoc.2024.0538 ) as well as from the IJOC GitHub software repository ( https:\/\/github.com\/INFORMSJoC\/2024.0538 ). The complete IJOC Software and Data Repository is available at https:\/\/informsjoc.github.io\/ .<\/jats:p>","DOI":"10.1287\/ijoc.2024.0538","type":"journal-article","created":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T14:52:59Z","timestamp":1757083979000},"page":"341-356","source":"Crossref","is-referenced-by-count":1,"title":["A New Upper Bound for the Euclidean TSP Constant"],"prefix":"10.1287","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5346-8529","authenticated-orcid":false,"given":"John Gunnar","family":"Carlsson","sequence":"first","affiliation":[{"name":"Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, California 90089"}]},{"given":"Julien","family":"Yu","sequence":"additional","affiliation":[{"name":"Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, California 90089"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2017.09.019"},{"key":"B2","volume-title":"The Traveling Salesman Problem","author":"Applegate DL","year":"2011"},{"key":"B3","unstructured":"Applegate DL, Cook WJ, Chv\u00e1tal V, Bixby RE (2015) Concorde TSP solver. Accessed January 15, 2025, https:\/\/www.math.uwaterloo.ca\/tsp\/concorde\/."},{"key":"B4","first-page":"113","author":"Avram F","year":"1992","journal-title":"Ann. Appl. Probability"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(82)90012-8"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.34.3.291"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100034095"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(89)90047-3"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(93)90145-D"},{"key":"B10","unstructured":"Border KC (2021) The law of small numbers. Lecture notes. Accessed January 15, 2025, https:\/\/healy.econ.ohio-state.edu\/kcb\/Ma103\/Notes\/Lecture13.pdf."},{"key":"B11","doi-asserted-by":"crossref","unstructured":"Carlsson JG, Yu J (2025) A new upper bound for the Euclidean TSP constant\n                      .\n                      https:\/\/doi.org\/10.1287\/ijoc.2024.0538.cd, https:\/\/github.com\/INFORMSJoC\/2024.0538.","DOI":"10.1287\/ijoc.2024.0538"},{"key":"B12","doi-asserted-by":"crossref","DOI":"10.1515\/9781400841103","volume-title":"In Pursuit of the Traveling Salesman","author":"Cook WJ","year":"2011"},{"key":"B13","volume-title":"Logistics Systems Analysis","author":"Daganzo C","year":"2005"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300000784"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)00033-I"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511550447"},{"key":"B17","first-page":"413","volume":"25","author":"Franceschetti A","year":"2017","journal-title":"Trans. Oper. Res."},{"key":"B18","unstructured":"FriCAS Team (2021) FriCAS\u2014An advanced computer algebra system. Accessed January 15, 2025, http:\/\/fricas.github.io\/."},{"key":"B19","doi-asserted-by":"crossref","unstructured":"Frieze A, Pegden W (2016) Separating subadditive Euclidean functionals.\n                      Proc. 48th Ann. ACM Sympos. Theory Comput.\n                      (ACM, New York), 22\u201335.","DOI":"10.1145\/2897518.2897571"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2019.11.007"},{"key":"B21","volume-title":"The Traveling Salesman Problem and Its Variations","volume":"12","author":"Gutin G","year":"2006"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1287\/opre.18.6.1138"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584070"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.93.038701"},{"key":"B25","unstructured":"Johansson F (2013) mpmath: A Python library for arbitrary-precision floating-point arithmetic (version 0.18). Accessed January 15, 2025, http:\/\/mpmath.org\/."},{"key":"B26","unstructured":"Johnson DS, McGeoch LA, Rothberg EE (1996) Asymptotic experimental analysis for the Held-Karp traveling salesman bound.\n                      Proc. 7th Ann. ACM-SIAM Sympos. Discrete Algorithms\n                      , vol. 341 (ACM Press, New York), 350."},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.50.R651"},{"key":"B28","volume-title":"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis","author":"Mitzenmacher M","year":"2017"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1016\/0960-0779(95)80046-J"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(89)90217-8"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.76.1188"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76361"},{"key":"B33","first-page":"1057","author":"Redmond C","year":"1994","journal-title":"Ann. Appl. Probability"},{"key":"B34","volume-title":"Space-Filling Curves","author":"Sagan H","year":"2012"},{"key":"B35","first-page":"365","author":"Steele JM","year":"1981","journal-title":"Ann. Probability"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970029"},{"key":"B37","unstructured":"Stein DM (1977) Scheduling dial-a-ride transportation systems: An asymptotic approach. Technical report, Division of Engineering and Applied Physics, Harvard University, Cambridge, MA."},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1239\/aap\/1427814579"},{"issue":"83","key":"B39","first-page":"463","volume":"46","author":"T\u00f3th LF","year":"1940","journal-title":"Math. Z"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(96)00214-7"},{"key":"B41","volume-title":"The Theory of Probability: Explorations and Applications","author":"Venkatesh SS","year":"2013"},{"key":"B42","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1951-0045403-1"},{"key":"B43","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2015.02.001"},{"key":"B44","volume-title":"Probability Theory of Classical Euclidean Optimization Problems","author":"Yukich JE","year":"2006"}],"container-title":["INFORMS Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/ijoc.2024.0538","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T08:25:35Z","timestamp":1776068735000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/ijoc.2024.0538"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["10.1287\/ijoc.2024.0538"],"URL":"https:\/\/doi.org\/10.1287\/ijoc.2024.0538","relation":{},"ISSN":["1091-9856","1526-5528"],"issn-type":[{"value":"1091-9856","type":"print"},{"value":"1526-5528","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3]]}}}