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

DOI10.1007/978-3-662-47672-7_70zbMath1440.68334MaRDI QIDQ3448843

Marvin Künnemann, Bodo Manthey

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-47672-7_70

Mathematics Subject Classification ID

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68W25: Approximation algorithms

Related Items

Improving TSP Tours Using Dynamic Programming over Tree Decompositions., Unnamed Item, The simultaneous semi-random model for TSP, Smoothed Analysis of Local Search Algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Smoothed performance guarantees for local search
• Performance guarantees for scheduling algorithms under perturbed machine speeds
• The Euclidean traveling salesman problem is NP-complete
• Probability theory of classical Euclidean optimization problems
• Smoothed analysis of partitioning algorithms for Euclidean functionals
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
• A Quantization Framework for Smoothed Analysis of Euclidean Optimization Problems
• Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise
• Worst-case and smoothed analysis of k-means clustering with Bregman divergences
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Worst-Case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-Means Method
• Smoothed analysis of algorithms
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• New Results on the Old k-opt Algorithm for the Traveling Salesman Problem
• Smoothed Analysis of the k-Means Method