An improved lower bound for the Traveling Salesman constant

Julia Gaudio*, Patrick Jaillet

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Let X1,X2,…,Xn be independent uniform random variables on [0,1]2. Let L(X1,…,Xn) be the length of the shortest Traveling Salesman tour through these points. Beardwood et al (1959) showed that there exists a constant β such that [Formula presented] almost surely. It was shown that β≥0.625. Building upon an approach proposed by Steinerberger (2015), we improve the lower bound to β≥0.6277.

Original languageEnglish (US)
Pages (from-to)67-70
Number of pages4
JournalOperations Research Letters
Volume48
Issue number1
DOIs
StatePublished - Jan 2020
Externally publishedYes

Keywords

  • Euclidean combinatorial optimization
  • Geometric probability
  • Traveling Salesman problem

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'An improved lower bound for the Traveling Salesman constant'. Together they form a unique fingerprint.

Cite this