Smoothed Approximation Ratio of the 2-Opt Heuristic for the TSP

Marvin Künnemann, Bodo Manthey

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

27 Downloads (Pure)

Abstract

The 2-Opt heuristic is a 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 prove an upper bound of exp(O(sqrt(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/log log 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 languageUndefined
Title of host publicationProceedings of the 13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization
EditorsA.F. Alkaya, E. Duman
Place of PublicationIstanbul, Turkey
PublisherÖzyegin Üniversitesi and Marmara Üniversitesi
Pages1-4
Number of pages4
ISBN (Print)not assigned
Publication statusPublished - 26 May 2015
Event13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2015 - Marmara University , Istanbul, Turkey
Duration: 26 May 201528 May 2015
Conference number: 13
http://ctw2015.eng.marmara.edu.tr/

Publication series

Name
PublisherÖzyegin Üniversitesi and Marmara Üniversitesi

Workshop

Workshop13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2015
Abbreviated titleCTW
CountryTurkey
CityIstanbul
Period26/05/1528/05/15
Internet address

Keywords

  • EWI-25941
  • IR-96321
  • METIS-312554
  • Smoothed Analysis
  • Traveling Salesman Problem

Cite this

Künnemann, M., & Manthey, B. (2015). Smoothed Approximation Ratio of the 2-Opt Heuristic for the TSP. In A. F. Alkaya, & E. Duman (Eds.), Proceedings of the 13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (pp. 1-4). Istanbul, Turkey: Özyegin Üniversitesi and Marmara Üniversitesi.
Künnemann, Marvin ; Manthey, Bodo. / Smoothed Approximation Ratio of the 2-Opt Heuristic for the TSP. Proceedings of the 13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization. editor / A.F. Alkaya ; E. Duman. Istanbul, Turkey : Özyegin Üniversitesi and Marmara Üniversitesi, 2015. pp. 1-4
@inproceedings{6832595c165a4825adae0fe179d749c0,
title = "Smoothed Approximation Ratio of the 2-Opt Heuristic for the TSP",
abstract = "The 2-Opt heuristic is a 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 prove an upper bound of exp(O(sqrt(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/log log 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.",
keywords = "EWI-25941, IR-96321, METIS-312554, Smoothed Analysis, Traveling Salesman Problem",
author = "Marvin K{\"u}nnemann and Bodo Manthey",
year = "2015",
month = "5",
day = "26",
language = "Undefined",
isbn = "not assigned",
publisher = "{\"O}zyegin {\"U}niversitesi and Marmara {\"U}niversitesi",
pages = "1--4",
editor = "A.F. Alkaya and E. Duman",
booktitle = "Proceedings of the 13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization",

}

Künnemann, M & Manthey, B 2015, Smoothed Approximation Ratio of the 2-Opt Heuristic for the TSP. in AF Alkaya & E Duman (eds), Proceedings of the 13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization. Özyegin Üniversitesi and Marmara Üniversitesi, Istanbul, Turkey, pp. 1-4, 13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2015, Istanbul, Turkey, 26/05/15.

Smoothed Approximation Ratio of the 2-Opt Heuristic for the TSP. / Künnemann, Marvin; Manthey, Bodo.

Proceedings of the 13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization. ed. / A.F. Alkaya; E. Duman. Istanbul, Turkey : Özyegin Üniversitesi and Marmara Üniversitesi, 2015. p. 1-4.

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

TY - GEN

T1 - Smoothed Approximation Ratio of the 2-Opt Heuristic for the TSP

AU - Künnemann, Marvin

AU - Manthey, Bodo

PY - 2015/5/26

Y1 - 2015/5/26

N2 - The 2-Opt heuristic is a 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 prove an upper bound of exp(O(sqrt(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/log log 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.

AB - The 2-Opt heuristic is a 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 prove an upper bound of exp(O(sqrt(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/log log 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.

KW - EWI-25941

KW - IR-96321

KW - METIS-312554

KW - Smoothed Analysis

KW - Traveling Salesman Problem

M3 - Conference contribution

SN - not assigned

SP - 1

EP - 4

BT - Proceedings of the 13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization

A2 - Alkaya, A.F.

A2 - Duman, E.

PB - Özyegin Üniversitesi and Marmara Üniversitesi

CY - Istanbul, Turkey

ER -

Künnemann M, Manthey B. Smoothed Approximation Ratio of the 2-Opt Heuristic for the TSP. In Alkaya AF, Duman E, editors, Proceedings of the 13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization. Istanbul, Turkey: Özyegin Üniversitesi and Marmara Üniversitesi. 2015. p. 1-4