Abstract
The 2-Opt heuristic is a very simple, easy-to-implement local search heuristic for the traveling salesman problem. While it usually provides good approximations to the optimal tour in experiments, its worst-case performance is poor.
In an attempt to explain the approximation performance of 2-Opt, we analyze the smoothed approximation ratio of 2-Opt. We obtain a bound of O(log(1/sigma)) for the smoothed approximation ratio of 2-Opt. As a lower bound, we prove that the worst-case lower bound of Omega(log n/loglog n) for the approximation ratio holds for sigma=O(1/sqrt(n)).
Our main technical novelty is that, different from existing smoothed analyses, we do not separately analyze objective values of the global and the local optimum on all inputs, but simultaneously bound them on the same input.
Original language | English |
---|---|
Title of host publication | Automata, Languages, and Programming |
Subtitle of host publication | 42nd International Colloquium on Automata, Languages and Programming (ICALP 2015) |
Editors | M.M. Halldorsson, K. Iwama, N. Kobayashi, B. Speckmann |
Place of Publication | Berlin |
Publisher | Springer |
Pages | 859-871 |
Number of pages | 13 |
ISBN (Electronic) | 978-3-662-47672-7 |
ISBN (Print) | 978-3-662-47671-0 |
DOIs | |
Publication status | Published - 20 Jun 2015 |
Event | 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015 - Kyoto, Japan Duration: 6 Jul 2015 → 10 Jul 2015 Conference number: 42 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer Verlag |
Volume | 9134 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015 |
---|---|
Abbreviated title | ICALP |
Country/Territory | Japan |
City | Kyoto |
Period | 6/07/15 → 10/07/15 |
Keywords
- EWI-25742
- Heuristics
- Traveling Salesman Problem
- METIS-312500
- IR-96323
- 2-opt
- Approximation algorithms
- Smoothed Analysis