DC Field
Value
Language
dc.contributor.author
Heimann, Sophia
-
dc.contributor.author
Hoang, Hung P.
-
dc.contributor.author
Hougardy, Stefan
-
dc.contributor.editor
Bringmann, Karl
-
dc.contributor.editor
Grohe, Martin
-
dc.contributor.editor
Puppis, Gabriele
-
dc.contributor.editor
Svensson, Ola
-
dc.date.accessioned
2025-01-13T17:03:55Z
-
dc.date.available
2025-01-13T17:03:55Z
-
dc.date.issued
2024
-
dc.identifier.citation
<div class="csl-bib-body"> <div class="csl-entry">Heimann, S., Hoang, H. P., &#38; Hougardy, S. (2024). The k-Opt Algorithm for the Traveling Salesman Problem Has Exponential Running Time for k ≥ 5. In K. Bringmann, M. Grohe, G. Puppis, &#38; O. Svensson (Eds.), <i>51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)</i>. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2024.84</div> </div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/208547
-
dc.description.abstract
The k-Opt algorithm is a local search algorithm for the Traveling Salesman Problem. Starting with an initial tour, it iteratively replaces at most k edges in the tour with the same number of edges to obtain a better tour. Krentel (FOCS 1989) showed that the Traveling Salesman Problem with the k-Opt neighborhood is complete for the class PLS (polynomial time local search) and that the k-Opt algorithm can have exponential running time for any pivot rule. However, his proof requires k ≫ 1000 and has a substantial gap. We show the two properties above for a much smaller value of k, addressing an open question by Monien, Dumrauf, and Tscheuschner (ICALP 2010). In particular, we prove the PLS-completeness for k ≥ 17 and the exponential running time for k ≥ 5.
en
dc.description.sponsorship
FWF - Österr. Wissenschaftsfonds
-
dc.language.iso
en
-
dc.relation.ispartofseries
Leibniz International Proceedings in Informatics (LIPIcs)
-
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
-
dc.subject
k-Opt algorithm
en
dc.subject
PLS-completeness
en
dc.subject
Traveling Salesman Problem
en
dc.title
The k-Opt Algorithm for the Traveling Salesman Problem Has Exponential Running Time for k ≥ 5
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.rights.license
Creative Commons Namensnennung 4.0 International
de
dc.rights.license
Creative Commons Attribution 4.0 International
en
dc.relation.publication
51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
-
dc.contributor.affiliation
University of Bonn, Germany
-
dc.contributor.affiliation
University of Bonn, Germany
-
dc.contributor.editoraffiliation
Saarland University, Germany
-
dc.contributor.editoraffiliation
RWTH Aachen University, Germany
-
dc.contributor.editoraffiliation
University of Udine, Italy
-
dc.contributor.editoraffiliation
École Polytechnique Fédérale de Lausanne, Switzerland
-
dc.relation.isbn
978-3-95977-322-5
-
dc.relation.grantno
Y1329-N
-
dc.rights.holder
© Sophia Heimann, Hung P. Hoang, and Stefan Hougardy
-
dc.type.category
Full-Paper Contribution
-
tuw.booktitle
51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
-
tuw.container.volume
297
-
tuw.peerreviewed
true
-
tuw.relation.publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
-
tuw.book.chapter
84
-
tuw.project.title
Parameterisierte Analyse in der Künstlichen Intelligenz
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
tuw.publisher.doi
10.4230/LIPIcs.ICALP.2024.84
-
dc.identifier.libraryid
AC17407946
-
dc.description.numberOfPages
18
-
tuw.author.orcid
0009-0000-9768-1815
-
tuw.author.orcid
0000-0001-7883-4134
-
tuw.author.orcid
0000-0001-8656-3418
-
dc.rights.identifier
CC BY 4.0
de
dc.rights.identifier
CC BY 4.0
en
tuw.editor.orcid
0000-0003-1356-5177
-
tuw.editor.orcid
0000-0001-9831-3264
-
tuw.editor.orcid
0000-0003-2551-3323
-
tuw.event.name
51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
en
dc.description.sponsorshipexternal
Deutsche Forschungsgemeinschaft (DFG)
-
dc.relation.grantnoexternal
390685813
-
tuw.event.startdate
08-07-2024
-
tuw.event.enddate
12-07-2024
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Tallinn
-
tuw.event.country
EE
-
tuw.event.presenter
Heimann, Sophia
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.openaccessfulltext
Open Access
-
item.grantfulltext
open
-
item.openairetype
conference paper
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.languageiso639-1
en
-
item.mimetype
application/pdf
-
item.fulltext
with Fulltext
-
item.cerifentitytype
Publications
-
crisitem.author.dept
University of Bonn, Germany
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
University of Bonn, Germany
-
crisitem.author.orcid
0009-0000-9768-1815
-
crisitem.author.orcid
0000-0001-7883-4134
-
crisitem.author.orcid
0000-0001-8656-3418
-
crisitem.author.parentorg
E192 - Institut für Logic and Computation
-
crisitem.project.funder
FWF - Österr. Wissenschaftsfonds
-
crisitem.project.grantno
Y1329-N
-
Appears in Collections:
Conference Paper
Thumbnail
Fulltext (Version of Record (published version))
Adobe PDF
(1.17 MB)
The k-Opt Algorithm for the Traveling Salesman Problem Has Exponential Running Time for k ≥ 5
Open Access CC BY 4.0
Show simple item record

Page view(s)

22
checked on Jan 13, 2025

Download(s)

3
checked on Jan 13, 2025

Google ScholarTM

Check