A New Upper Bound for the Euclidean TSP Constant

References

• Ansari S, Başdere M, Li X, Ouyang Y, Smilowitz K (2018) Advancements in continuous approximation models for logistics and transportation systems: 1996–2016. Transportation Res. Part B Methodological 107:229–252.Crossref, Google Scholar
• Applegate DL, Bixby RE, Chvátal V, Cook WJ (2011) The traveling salesman problem. The Traveling Salesman Problem (Princeton University Press, Princeton, NJ).Google Scholar
• Applegate DL, Cook WJ, Chvátal V, Bixby RE (2015) Concorde TSP solver. Accessed January 15, 2025, https://www.math.uwaterloo.ca/tsp/concorde/.Google Scholar
• Avram F, Bertsimas D (1992) The minimum spanning tree constant in geometrical probability and under the independent model: A unified approach. Ann. Appl. Probability 2(1):113–130.Google Scholar
• Bartholdi JJ III, Platzman LK (1982) An O (N log N) planar traveling salesman heuristic based on spacefilling curves. Oper. Res. Lett. 1(4):121–125.Crossref, Google Scholar
• Bartholdi JJ III, Platzman LK (1988) Heuristics based on spacefilling curves for combinatorial problems in Euclidean space. Management Sci. 34(3):291–305.Link, Google Scholar
• Beardwood J, Halton JH, Hammersley JM (1959) The shortest path through many points. Mathematical Proceedings of the Cambridge Philosophical Society, vol. 55 (Cambridge University Press, Cambridge, UK), 299–327.Crossref, Google Scholar
• Bertsimas D, Grigni M (1989) Worst-case examples for the spacefilling curve heuristic for the Euclidean traveling salesman problem. Oper. Res. Lett. 8(5):241–244.Crossref, Google Scholar
• Bertsimas D, Howell LH (1993) Further results on the probabilistic traveling salesman problem. Eur. J. Oper. Res. 65(1):68–95.Crossref, Google Scholar
• 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.Google Scholar
• Carlsson JG, Yu J (2025) A new upper bound for the Euclidean TSP constant. https://doi.org/10.1287/ijoc.2024.0538.cd, https://github.com/INFORMSJoC/2024.0538.Google Scholar
• Cook WJ (2011) In pursuit of the traveling salesman. In Pursuit of the Traveling Salesman (Princeton University Press, Princeton, NJ).Google Scholar
• Daganzo C (2005) Logistics Systems Analysis, 3rd ed. (Springer Science & Business Media, Berlin, Heidelberg).Google Scholar
• Few L (1955) The shortest path and the shortest road through n points. Mathematika 2(2):141–144.Crossref, Google Scholar
• Fiechter C-N (1994) A parallel tabu search algorithm for large traveling salesman problems. Discrete Appl. Math. 51(3):243–267.Crossref, Google Scholar
• Finch SR (2003) Mathematical Constants (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Franceschetti A, Jabali O, Laporte G (2017) Continuous approximation models in freight distribution management. Trans. Oper. Res. 25:413–433.Google Scholar
• FriCAS Team (2021) FriCAS—An advanced computer algebra system. Accessed January 15, 2025, http://fricas.github.io/.Google Scholar
• Frieze A, Pegden W (2016) Separating subadditive Euclidean functionals. Proc. 48th Ann. ACM Sympos. Theory Comput. (ACM, New York), 22–35.Google Scholar
• Gaudio J, Jaillet P (2020) An improved lower bound for the traveling salesman constant. Oper. Res. Lett. 48(1):67–70.Crossref, Google Scholar
• Gutin G, Punnen AP (2006) The Traveling Salesman Problem and Its Variations, vol. 12 (Springer Science & Business Media, Berlin, Heidelberg).Google Scholar
• Held M, Karp RM (1970) The traveling-salesman problem and minimum spanning trees. Oper. Res. 18(6):1138–1162.Link, Google Scholar
• Held M, Karp RM (1971) The traveling-salesman problem and minimum spanning trees: Part II. Math. Programming 1(1):6–25.Crossref, Google Scholar
• Jacobsen J-L, Read N, Saleur H (2004) Traveling salesman problem, conformal invariance, and dense polymers. Phys. Rev. Lett. 93(3):038701.Crossref, Google Scholar
• Johansson F (2013) mpmath: A Python library for arbitrary-precision floating-point arithmetic (version 0.18). Accessed January 15, 2025, http://mpmath.org/.Google Scholar
• Johnson DS, McGeoch LA, Rothberg EE (1996) Asymptotic experimental analysis for the Held-Karp traveling salesman bound. Proc. 7th Ann. ACM-SIAM Sympos. Discrete Algorithms, vol. 341 (ACM Press, New York), 350.Google Scholar
• Lee J, Choi M (1994) Optimization by multicanonical annealing and the traveling salesman problem. Phys. Rev. E 50(2):R651.Crossref, Google Scholar
• Mitzenmacher M, Upfal E (2017) Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis (Cambridge University Press).Google Scholar
• Norman MG, Moscato P (1995) The Euclidean traveling salesman problem and a space-filling curve. Chaos Solitons Fractals 6:389–397.Crossref, Google Scholar
• Ong HL, Huang HC (1989) Asymptotic expected performance of some TSP heuristics: An empirical evaluation. Eur. J. Oper. Res. 43(2):231–238.Crossref, Google Scholar
• Percus AG, Martin OC (1996) Finite size and dimensional dependence in the Euclidean traveling salesman problem. Phys. Rev. Lett. 76(8):1188.Crossref, Google Scholar
• Platzman LK, Bartholdi JJ III (1989) Spacefilling curves and the planar traveling salesman problem. J. ACM 36(4):719–737.Crossref, Google Scholar
• Redmond C, Yukich JE (1994) Limit theorems and rates of convergence for Euclidean functionals. Ann. Appl. Probability 4(4):1057–1073.Google Scholar
• Sagan H (2012) Space-Filling Curves (Springer Science & Business Media, Berlin, Heidelberg).Google Scholar
• Steele JM (1981) Subadditive Euclidean functionals and nonlinear growth in geometric probability. Ann. Probability 9(3):365–376.Google Scholar
• Steele JM (1997) Probability Theory and Combinatorial Optimization (SIAM, Philadelphia).Crossref, Google Scholar
• Stein DM (1977) Scheduling dial-a-ride transportation systems: An asymptotic approach. Technical report, Division of Engineering and Applied Physics, Harvard University, Cambridge, MA.Google Scholar
• Steinerberger S (2015) New bounds for the traveling salesman constant. Adv. Appl. Probability 47(1):27–36.Crossref, Google Scholar
• Tóth LF (1940) Über einen geometrischen Satz. Math. Z 46(83–85):463.Google Scholar
• Valenzuela CL, Jones AJ (1997) Estimating the Held-Karp lower bound for the geometric TSP. Eur. J. Oper. Res. 102(1):157–175.Crossref, Google Scholar
• Venkatesh SS (2013) The Theory of Probability: Explorations and Applications (Cambridge University Press, Cambridge, UK).Google Scholar
• Verblunsky S (1951) On the shortest path through a number of points. Proc. Amer. Math. Soc. 2(6):904–913.Crossref, Google Scholar
• Xie W, Ouyang Y (2015) Optimal layout of transshipment facility locations on an infinite homogeneous plane. Transportation Res. Part B Methodological 75:74–88.Crossref, Google Scholar
• Yukich JE (2006) Probability Theory of Classical Euclidean Optimization Problems (Springer, Berlin, Heidelberg).Google Scholar