New Bounds for the Traveling Salesman Constant

DOI10.1239/AAP/1427814579zbMATH Open1309.60005arXiv1311.6338OpenAlexW2963958826WikidataQ63198871 ScholiaQ63198871MaRDI QIDQ5246169FDOQ5246169

Authors: Stefan Steinerberger 

Publication date: 17 April 2015

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

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.

Full work available at URL: https://arxiv.org/abs/1311.6338

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

zbMATH Keywords

Beardwood-Halton-Hammersley theoremtraveling salesman constant

Mathematics Subject Classification ID

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

Cites Work

• The traveling salesman problem. A computational study.
• The traveling salesman problem and its variations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The theory of probability. Explorations and applications
• Title not available (Why is that?)
• In pursuit of the traveling salesman. Mathematics at the limits of computation
• 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
• Estimating the Held-Karp lower bound for the geometric TSP
• Subadditive Euclidean functionals and nonlinear growth in geometric probability
• Finite Size and Dimensional Dependence in the Euclidean Traveling Salesman Problem
• On the Shortest Path Through a Number of Points
• Über einen geometrischen Satz
• Limit theorems and rates of convergence for Euclidean functionals

Cited In (17)

• How Long Can a Euclidean Traveling Salesman Tour Be?
• Title not available (Why is that?)
• Euclidean travelling salesman problem with location-dependent and power-weighted edges
• 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
• Temporal Traveling Salesman Problem – in a Logic- and Graph Theory-Based Depiction
• Traveling salesman problem across well-connected cities and with location-dependent edge lengths
• 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
• Iterated tour partitioning for Euclidean capacitated vehicle routing

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)