Truly tight bounds for TSP heuristics

Cor Hurkens

doi:10.1016/j.orl.2023.06.003

Truly tight bounds for TSP heuristics

Cor Hurkens (Corresponding author)

Combinatorial Optimization

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

63 Downloads (Pure)

Abstract

We present an improved performance analysis of select-and-extend heuristics for the metric traveling salesman problem. Our main contributions concern the Arbitrary Addition and Farthest Addition methods.

Original language	English
Pages (from-to)	425-431
Number of pages	7
Journal	Operations Research Letters
Volume	51
Issue number	4
DOIs	https://doi.org/10.1016/j.orl.2023.06.003
Publication status	Published - Jul 2023

Bibliographical note

Funding Information:
I dedicate this work to the memory of Gerhard Woeginger, who encouraged me to publish these results.

Publisher Copyright:
© 2023 The Author(s)

Keywords

Matching bounds
TSP-heuristics
Worst-case analysis

Access to Document

10.1016/j.orl.2023.06.003

pdfFinal published version, 362 KBLicence: CC BY

Cite this

@article{458c591bf4ca48b2ac213f14e2dd9d24,

title = "Truly tight bounds for TSP heuristics",

abstract = "We present an improved performance analysis of select-and-extend heuristics for the metric traveling salesman problem. Our main contributions concern the Arbitrary Addition and Farthest Addition methods.",

keywords = "Matching bounds, TSP-heuristics, Worst-case analysis",

author = "Cor Hurkens",

note = "Funding Information: I dedicate this work to the memory of Gerhard Woeginger, who encouraged me to publish these results. Publisher Copyright: {\textcopyright} 2023 The Author(s)",

year = "2023",

month = jul,

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

language = "English",

volume = "51",

pages = "425--431",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "4",

}

TY - JOUR

T1 - Truly tight bounds for TSP heuristics

AU - Hurkens, Cor

PY - 2023/7

Y1 - 2023/7

N2 - We present an improved performance analysis of select-and-extend heuristics for the metric traveling salesman problem. Our main contributions concern the Arbitrary Addition and Farthest Addition methods.

AB - We present an improved performance analysis of select-and-extend heuristics for the metric traveling salesman problem. Our main contributions concern the Arbitrary Addition and Farthest Addition methods.

KW - Matching bounds

KW - TSP-heuristics

KW - Worst-case analysis

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

U2 - 10.1016/j.orl.2023.06.003

DO - 10.1016/j.orl.2023.06.003

M3 - Article

AN - SCOPUS:85163150480

SN - 0167-6377

VL - 51

SP - 425

EP - 431

JO - Operations Research Letters

JF - Operations Research Letters

IS - 4

ER -

Truly tight bounds for TSP heuristics

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this