Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic

Marvin Künnemann, Bodo Manthey

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

6 Citations (Scopus)

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 languageEnglish
Title of host publicationAutomata, Languages, and Programming
Subtitle of host publication42nd International Colloquium on Automata, Languages and Programming (ICALP 2015)
EditorsM.M. Halldorsson, K. Iwama, N. Kobayashi, B. Speckmann
Place of PublicationBerlin
PublisherSpringer
Pages859-871
Number of pages13
ISBN (Electronic)978-3-662-47672-7
ISBN (Print)978-3-662-47671-0
DOIs
Publication statusPublished - 20 Jun 2015
Event42nd International Colloquium on Automata, Languages and Programming, ICALP 2015 - Kyoto, Japan
Duration: 6 Jul 201510 Jul 2015
Conference number: 42

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume9134
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference42nd International Colloquium on Automata, Languages and Programming, ICALP 2015
Abbreviated titleICALP
CountryJapan
CityKyoto
Period6/07/1510/07/15

Keywords

  • EWI-25742
  • Heuristics
  • Traveling Salesman Problem
  • METIS-312500
  • IR-96323
  • 2-opt
  • Approximation algorithms
  • Smoothed Analysis

Fingerprint Dive into the research topics of 'Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic'. Together they form a unique fingerprint.

Cite this