On the Complexity of the Metric TSP under Stability Considerations

Matúš Mihalák, Marcel Schöngens, Rastislav Šrámek, Peter Widmayer

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Abstract

We consider the metric Traveling Salesman Problem (Δ-TSP for short) and study how stability (as defined by Bilu and Linial [3]) influences the complexity of the problem. On an intuitive level, an instance of Δ-TSP is γ-stable (γ>1), if there is a unique optimum Hamiltonian tour and any perturbation of arbitrary edge weights by at most γ does not change the edge set of the optimal solution (i.e., there is a significant gap between the optimum tour and all other tours). We show that for γ ≥ 1.8 a simple greedy algorithm (resembling Prim’s algorithm for constructing a minimum spanning tree) computes the optimum Hamiltonian tour for every γ-stable instance of the Δ-TSP, whereas a simple local search algorithm can fail to find the optimum even if γ is arbitrary. We further show that there are γ-stable instances of Δ-TSP for every 1
Original languageEnglish
Title of host publicationProceedings of the 37th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)
Pages382-393
Number of pages12
DOIs
Publication statusPublished - 2011
Externally publishedYes

Cite this