The Library
Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
Tools
Englert, Matthias, Röglin, Heiko and Vöcking, Berthold (2014) Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP. Algorithmica, Volume 68 (Number 1). pp. 190-264. doi:10.1007/s00453-013-9801-4 ISSN 0178-4617.
|
PDF
WRAP_Engler_art%3A10.1007%2Fs00453-013-9801-4.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (2272Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/s00453-013-9801-4
Abstract
2-Opt is probably the most basic local search heuristic for the TSP. This heuristic achieves amazingly good results on “real world” Euclidean instances both with respect to running time and approximation ratio. There are numerous experimental studies on the performance of 2-Opt. However, the theoretical knowledge about this heuristic is still very limited. Not even its worst case running time on 2-dimensional Euclidean instances was known so far. We clarify this issue by presenting, for every p∈N , a family of L p instances on which 2-Opt can take an exponential number of steps.
Previous probabilistic analyses were restricted to instances in which n points are placed uniformly at random in the unit square [0,1]2, where it was shown that the expected number of steps is bounded by O~(n10) for Euclidean instances. We consider a more advanced model of probabilistic instances in which the points can be placed independently according to general distributions on [0,1] d , for an arbitrary d≥2. In particular, we allow different distributions for different points. We study the expected number of local improvements in terms of the number n of points and the maximal density ϕ of the probability distributions. We show an upper bound on the expected length of any 2-Opt improvement path of O~(n4+1/3⋅ϕ8/3) . When starting with an initial tour computed by an insertion heuristic, the upper bound on the expected number of steps improves even to O~(n4+1/3−1/d⋅ϕ8/3) . If the distances are measured according to the Manhattan metric, then the expected number of steps is bounded by O~(n4−1/d⋅ϕ) . In addition, we prove an upper bound of O(ϕ√d) on the expected approximation factor with respect to all L p metrics.
Let us remark that our probabilistic analysis covers as special cases the uniform input model with ϕ=1 and a smoothed analysis with Gaussian perturbations of standard deviation σ with ϕ∼1/σ d .
Item Type: | Journal Article | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software T Technology > T Technology (General) |
||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||
Library of Congress Subject Headings (LCSH): | Probabilities, Computer science -- Mathematics, Heuristic programming, Programming (Mathematics), Heuristic algorithms, Traveling salesman problem | ||||||||||
Journal or Publication Title: | Algorithmica | ||||||||||
Publisher: | Springer Verlag | ||||||||||
ISSN: | 0178-4617 | ||||||||||
Official Date: | January 2014 | ||||||||||
Dates: |
|
||||||||||
Volume: | Volume 68 | ||||||||||
Number: | Number 1 | ||||||||||
Page Range: | pp. 190-264 | ||||||||||
DOI: | 10.1007/s00453-013-9801-4 | ||||||||||
Status: | Peer Reviewed | ||||||||||
Publication Status: | Published | ||||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||||
Date of first compliant deposit: | 26 December 2015 | ||||||||||
Date of first compliant Open Access: | 26 December 2015 | ||||||||||
Funder: | European Commission (EC), Deutsche Forschungsgemeinschaft (DFG), Engineering and Physical Sciences Research Council (EPSRC) | ||||||||||
Grant number: | 001907 (DELIS) (EC), VO 889/2 (DFG), WE 2842/1 (DFG), EP/F043333/1 | ||||||||||
Embodied As: | 1 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year