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

35 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.