Smoothed analysis of the 2-Opt algorithm for the general TSP

DOI10.1145/2972953MaRDI QIDQ4962645zbMATH OpenOpenAlexFDO

Authors Matthias Englert, Heiko Röglin, Berthold Vöcking

Publication date 5 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL http://wrap.warwick.ac.uk/81525/7/WRAP_0771998-cs-120916-2-opt.pdf

zbMATH Keywords

2-Optlocal searchprobabilistic analysissmoothed analysistraveling salesperson problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP (extended abstract)
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
• Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise
• Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
• scientific article; zbMATH DE number 1054958

Cited in

(18)

• Average-case approximation ratio of the 2-opt algorithm for the TSP
• The simultaneous semi-random model for TSP
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
• Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP (extended abstract)
• Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
• Smoothed Analysis of Local Search
• Mechanism design for perturbation stable combinatorial auctions
• The smoothed complexity of policy iteration for Markov decision processes
• Approximation ineffectiveness of a tour-untangling heuristic
• The simultaneous semi-random model for TSP
• On the smoothed complexity of combinatorial local search
• Worst-case and smoothed analysis of the hartigan-Wong method for k-means clustering
• Improved smoothed analysis of 2-opt for the Euclidean TSP
• Performance of efficient variants of the 2-opt heuristic for the traveling salesperson problem
• Improved smoothed analysis of 2-opt for the Euclidean TSP
• Counting locally optimal tours in the TSP
• Smoothed analysis of online metric problems

This page was built for publication: Smoothed analysis of the 2-Opt algorithm for the general TSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4962645)