Deterministic 7/8-approximation for the metric maximum TSP (Q1034619)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Deterministic 7/8-approximation for the metric maximum TSP |
scientific article |
Statements
Deterministic 7/8-approximation for the metric maximum TSP (English)
0 references
6 November 2009
0 references
The authors present the first deterministic 7/8-approximation algorithm for the maximum traveling salesman problem (MAX-TSP) in complete metric graphs. The first approach is based on a maximum cycle cover: the lightest edge in each cycle is removed, while the actual set of paths is enlarged by certain edges to get a Hamiltonian cycle. The second approach processes the cycles of an maximum cycle cover in a certain order, which is based on so-called loose-ends (vertices), and determines certain heavy edges, which are added successively to a maximum matching resulting finally in a Hamiltonian cycle. The heavier of both resulting Hamiltonian cycles gives a 7/8 approximation guarantee in case of graphs with an even number of vertices. For an odd number of vertices a (perhaps avoidable) overhead of \(O(n^4)\) in the time complexity -- induced by matching-cover pairs -- is a significant drawback for practical use.
0 references
maximum TSP
0 references
matching
0 references
cycle cover
0 references
approximation
0 references