×

TSP heuristics: domination analysis and complexity. (English) Zbl 1060.90075

Summary: 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 \(\lceil{n}/{2}\rceil!\), 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 \(\vec{K}_n\) 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) \equiv 0\pmod{k+1}\). The complexities of finding the median value of costs of all the tours in \(\vec{K}_n\) and of similar problems are also studied.

MSC:

90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming
90C60 Abstract computational complexity for mathematical programming problems
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI