Smoothed Analysis of the 2-Opt Algorithm for the General TSP

DOI10.1145/2972953zbMath1445.68370OpenAlexW2519455498MaRDI QIDQ4962645

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

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

local searchprobabilistic analysissmoothed analysistraveling salesperson problem2-Opt

Mathematics Subject Classification ID

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

Related Items (2)

The simultaneous semi-random model for TSP ⋮ Mechanism design for perturbation stable combinatorial auctions

This page was built for publication: Smoothed Analysis of the 2-Opt Algorithm for the General TSP