Reassembling trees for the traveling salesman
| Autor: | Jens Vygen |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) General Mathematics 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology Minimum spanning tree 01 natural sciences Distributed minimum spanning tree Combinatorics Kruskal's algorithm Euclidean minimum spanning tree Computer Science - Data Structures and Algorithms FOS: Mathematics Mathematics - Combinatorics Data Structures and Algorithms (cs.DS) Minimum degree spanning tree Mathematics Discrete mathematics 021103 operations research Spanning tree 010201 computation theory & mathematics Christofides algorithm Combinatorial optimization Combinatorics (math.CO) Computer Science - Discrete Mathematics |
| Popis: | Many recent approximation algorithms for different variants of the traveling salesman problem (asymmetric TSP, graph TSP, s-t-path TSP) exploit the well-known fact that a solution of the natural linear programming relaxation can be written as convex combination of spanning trees. The main argument then is that randomly sampling a tree from such a distribution and then completing the tree to a tour at minimum cost yields a better approximation guarantee than simply taking a minimum cost spanning tree (as in Christofides' algorithm). We argue that an additional step can help: reassembling the spanning trees before sampling. Exchanging two edges in a pair of spanning trees can improve their properties under certain conditions. We demonstrate the usefulness for the metric s-t-path TSP by devising a deterministic polynomial-time algorithm that improves on Seb\H{o}'s previously best approximation ratio of 8/5. Comment: minor revision, final version, to appear in SIAM Journal of Discrete Mathematics, please use color printer |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|