New Bounds for the Traveling Salesman Constant

DOI10.1239/AAP/1427814579MaRDI QIDQ5246169zbMATH OpenOpenAlexWikidataFDO

Authors Stefan Steinerberger

Publication date 17 April 2015

Published in Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.6338, https://projecteuclid.org/euclid.aap/1427814579

zbMATH Keywords

Beardwood-Halton-Hammersley theoremtraveling salesman constant

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Functional limit theorems; invariance principles (60F17)

Abstract: Let $X_1,X_2,dots,X_n$ be independent and uniformly distributed random variables in the unit square $[0,1{]}^2$ and let $L(X_1,dots,X_n)$ be the length of the shortest traveling salesman path through these points. In 1959, Beardwood, Halton $$ Hammersley proved the existence of a universal constant $$ such that ${\displaystyle }$ lim_{n ightarrow infty}{n^{-1/2}L(X_1, dots, X_n)} = �eta qquad mbox{almost surely.}${\displaystyle }$ The best bounds for $$ are still the ones originally established by Beardwood, Halton $$ Hammersley $$. We slightly improve both upper and lower bounds.

Recommendations

• An improved lower bound for the traveling salesman constant
• A new generalization of the traveling salesman problem
• Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
• New lower bounds for the symmetric travelling salesman problem
• Optimal bounds for the analytical traveling salesman problem
• Improving Christofides' lower bound for the traveling salesman problem
• A New Formulation for the Travelling Salesman Problem
• Algorithms for solution of the travelling salesman problem. II: New lower bound
• scientific article; zbMATH DE number 1855663
• The traveling salesman problem: new polynomial approximation algorithms and domination analysis

Cites work

• scientific article; zbMATH DE number 52632 (Why is no real title available?)
• scientific article; zbMATH DE number 871931 (Why is no real title available?)
• scientific article; zbMATH DE number 1414606 (Why is no real title available?)
• scientific article; zbMATH DE number 3193293 (Why is no real title available?)
• Estimating the Held-Karp lower bound for the geometric TSP
• Finite Size and Dimensional Dependence in the Euclidean Traveling Salesman Problem
• In pursuit of the traveling salesman. Mathematics at the limits of computation
• Limit theorems and rates of convergence for Euclidean functionals
• On the Shortest Path Through a Number of Points
• Subadditive Euclidean functionals and nonlinear growth in geometric probability
• The minimum spanning tree constant in geometrical probability and under the independent model: A unified approach
• The shortest path and the shortest road through n points
• The theory of probability. Explorations and applications
• The traveling salesman problem and its variations
• The traveling salesman problem. A computational study.
• Über einen geometrischen Satz

Cited in

(17)

• Iterated tour partitioning for Euclidean capacitated vehicle routing
• How Long Can a Euclidean Traveling Salesman Tour Be?
• Euclidean travelling salesman problem with location-dependent and power-weighted edges
• scientific article; zbMATH DE number 4194815 (Why is no real title available?)
• Bounds for the traveling salesman paths of two-dimensional modular lattices
• Randomized near-neighbor graphs, giant components and applications in data science
• A new lower bound for the geometric traveling salesman problem in terms of discrepancy
• New lower bounds for the symmetric travelling salesman problem
• Route efficiency implications of time windows and vehicle capacities in first- and last-mile logistics
• Traveling salesman problem across well-connected cities and with location-dependent edge lengths
• Temporal Traveling Salesman Problem – in a Logic- and Graph Theory-Based Depiction
• An improved lower bound for the traveling salesman constant
• Continuous approximation formulas for location problems
• On global integer extrema of real-valued box-constrained multivariate quadratic functions
• Boundary effects in the traveling salesperson problem
• New Monitoring Parameter for the Traveling Salesman Problem
• A Priori Bounds on the Euclidean Traveling Salesman

Describes a project that uses

Uses Software

• Concorde

This page was built for publication: New Bounds for the Traveling Salesman Constant

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5246169)