Deterministic 7/8-approximation for the metric maximum TSP (Q1034619): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.tcs.2009.07.051 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W3021112015 / rank | |||
Normal rank |
Revision as of 21:31, 19 March 2024
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