New Bounds for the Traveling Salesman Constant

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

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

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The traveling salesman problem and its variations
• In Pursuit of the Traveling Salesman
• 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 (13)

• 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
• New Monitoring Parameter for the Traveling Salesman Problem
• Iterated tour partitioning for Euclidean capacitated vehicle routing

Uses Software

• Concorde

Recommendations

• A New Formulation for the Travelling Salesman Problem 👍 👎
• Improved Lower Bounds on the Approximability of the Traveling Salesman Problem 👍 👎
• Algorithms for solution of the travelling salesman problem. II: New lower bound 👍 👎
• New lower bounds for the symmetric travelling salesman problem 👍 👎
• The traveling salesman problem: new polynomial approximation algorithms and domination analysis 👍 👎
• Improving Christofides' lower bound for the traveling salesman problem 👍 👎
• An improved lower bound for the traveling salesman constant 👍 👎
• Optimal bounds for the analytical traveling salesman problem 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

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)