Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise

DOI10.1007/978-3-642-45030-3_54zbMath1407.90277OpenAlexW1923505183MaRDI QIDQ2872122

Bodo Manthey, Rianne Veenstra

Publication date: 14 January 2014

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-45030-3_54

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (5)

Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic ⋮ Smoothed Analysis of Local Search Algorithms ⋮ Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem ⋮ Random shortest paths: non-Euclidean instances for metric optimization problems ⋮ Improving TSP Tours Using Dynamic Programming over Tree Decompositions.

This page was built for publication: Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise