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

DOI10.1007/978-3-662-47672-7_70zbMath1440.68334OpenAlexW1923819040MaRDI 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

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Related Items (4)

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

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

This page was built for publication: Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic