TSP Heuristics: Domination Analysis and Complexity |
| |
Authors: | Punnen Margot and Kabadi |
| |
Affiliation: | (1) Department of Mathematical Sciences, University of New Brunswick, Saint John, New Brunswick, Canada E2L 4L5. punnen@unbsj.ca., CA;(2) Department of Mathematics, University of Kentucky, Lexington, KY 40506-0027, USA. fmargot@ms.uky.edu., US;(3) Faculty of Administration, University of New Brunswick, Fredericton, New Brunswick, Canada E3B 5A4. kabadi@unb.ca., CA |
| |
Abstract: |
Abstract. We show that the 2-Opt and 3-Opt heuristics for the traveling salesman problem (TSP) on the complete graph K
n
produce a solution no worse than the average cost of a tour in K
n
in a polynomial number of iterations. As a consequence, we get that the domination numbers of the 2- Opt , 3- Opt , Carlier—Villon,
Shortest Path Ejection Chain, and Lin—Kernighan heuristics are all at least (n-2)! / 2 . The domination number of the Christofides heuristic is shown to be no more than , and for the Double Tree heuristic and a variation of the Christofides heuristic the domination numbers are shown to be
one (even if the edge costs satisfy the triangle inequality). Further, unless P = NP, no polynomial time approximation algorithm
exists for the TSP on the complete digraph with domination number at least (n-1)!-k for any constant k or with domination number at least (n-1)! - (( k /(k+1))(n+r))!-1 for any non-negative constants r and k such that (n+r) 0 mod (k+1). The complexities of finding the median value of costs of all the tours in and of similar problems are also studied. |
| |
Keywords: | , Domination analysis, Approximation algorithms, Traveling salesman problem, Computational complexity, |
本文献已被 SpringerLink 等数据库收录! |
|