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

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

2 Citaten (Scopus)

83 Downloads (Pure)

Samenvatting

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.

Originele taal-2	Engels
Pagina's (van-tot)	425-431
Aantal pagina's	7
Tijdschrift	Operations Research Letters
Volume	51
Nummer van het tijdschrift	4
DOI's	https://doi.org/10.1016/j.orl.2023.06.003
Status	Gepubliceerd - jul. 2023

Bibliografische nota

Publisher Copyright:
© 2023 The Author(s)

Financiering

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

Toegang tot document

10.1016/j.orl.2023.06.003

pdfDefinitieve gepubliceerde versie, 362 KBLicentie: CC BY

Andere bestanden en links

Link naar publicatie in Scopus

Citeer dit

@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 B.V.",

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

Samenvatting

Bibliografische nota

Financiering

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit