An improved lower bound for the Traveling Salesman constant

Julia Gaudio; Patrick Jaillet

doi:10.1016/j.orl.2019.11.007

An improved lower bound for the Traveling Salesman constant

Julia Gaudio^*, Patrick Jaillet

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

Let X₁,X₂,…,X_n be independent uniform random variables on [0,1]². Let L(X₁,…,X_n) 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 language	English (US)
Pages (from-to)	67-70
Number of pages	4
Journal	Operations Research Letters
Volume	48
Issue number	1
DOIs	https://doi.org/10.1016/j.orl.2019.11.007
State	Published - Jan 2020
Externally published	Yes

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

Access to Document

10.1016/j.orl.2019.11.007

Cite this

@article{c8aa03294ace4de781057c09697b58fc,

title = "An improved lower bound for the Traveling Salesman constant",

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.",

keywords = "Euclidean combinatorial optimization, Geometric probability, Traveling Salesman problem",

author = "Julia Gaudio and Patrick Jaillet",

note = "Funding Information: Julia Gaudio is supported by a Microsoft Research, United States of America PhD Fellowship. Publisher Copyright: {\textcopyright} 2019 Elsevier B.V.",

year = "2020",

month = jan,

doi = "10.1016/j.orl.2019.11.007",

language = "English (US)",

volume = "48",

pages = "67--70",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - An improved lower bound for the Traveling Salesman constant

AU - Gaudio, Julia

AU - Jaillet, Patrick

PY - 2020/1

Y1 - 2020/1

N2 - 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.

AB - 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.

KW - Euclidean combinatorial optimization

KW - Geometric probability

KW - Traveling Salesman problem

UR - http://www.scopus.com/inward/record.url?scp=85076482765&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85076482765&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2019.11.007

DO - 10.1016/j.orl.2019.11.007

M3 - Article

AN - SCOPUS:85076482765

SN - 0167-6377

VL - 48

SP - 67

EP - 70

JO - Operations Research Letters

JF - Operations Research Letters

IS - 1

ER -

An improved lower bound for the Traveling Salesman constant

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this