Improved Smoothed Analysis of 2-Opt for the Euclidean TSP

Bodo Manthey, Jesse van Rhijn*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

28 Downloads (Pure)

Abstract

The 2-opt heuristic is a simple local search heuristic for the Travelling Salesperson Problem (TSP). Although it usually performs well in practice, its worst-case running time is poor. Attempts to reconcile this difference have used smoothed analysis, in which adversarial instances are perturbed probabilistically. We are interested in the classical model of smoothed analysis for the Euclidean TSP, in which the perturbations are Gaussian. This model was previously used by Manthey & Veenstra, who obtained smoothed complexity bounds polynomial in n, the dimension d, and the perturbation strength σ1. However, their analysis only works for d ≥ 4. The only previous analysis for d ≤ 3 was performed by Englert, Röglin & Vöcking, who used a different perturbation model which can be translated to Gaussian perturbations. Their model yields bounds polynomial in n and σ−d, and super-exponential in d. As the fact that no direct analysis exists for Gaussian perturbations that yields polynomial bounds for all d is somewhat unsatisfactory, we perform this missing analysis. Along the way, we improve all existing smoothed complexity bounds for Euclidean 2-opt with Gaussian perturbations.

Original languageEnglish
Title of host publication34th International Symposium on Algorithms and Computation (ISAAC 2023)
EditorsSatoru Iwata, Satoru Iwata, Naonori Kakimura
PublisherDagstuhl
Number of pages16
ISBN (Electronic)978-3-95977-289-1
DOIs
Publication statusPublished - 28 Nov 2023
Event34th International Symposium on Algorithms and Computation, ISAAC 2023 - Kyoto, Japan
Duration: 3 Dec 20236 Dec 2023
Conference number: 34

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume283
ISSN (Print)1868-8969

Conference

Conference34th International Symposium on Algorithms and Computation, ISAAC 2023
Abbreviated titleISAAC 2023
Country/TerritoryJapan
CityKyoto
Period3/12/236/12/23

Keywords

  • 2-opt
  • heuristics
  • local search
  • probabilistic analysis
  • smoothed analysis
  • Travelling salesman problem

Fingerprint

Dive into the research topics of 'Improved Smoothed Analysis of 2-Opt for the Euclidean TSP'. Together they form a unique fingerprint.

Cite this