| Autor: |
Liśkiewicz, Maciej, Reischuk, Rüdiger, Bläser, M., Ram, L. Shankar |
| Zdroj: |
Fundamentals of Computation Theory (9783540281931); 2005, p504-515, 12p |
| Abstrakt: |
The minimum traveling salesman problem with distances one and two is the following problem: Given a complete undirected graph G=(V,E) with a cost function w: E→ {1, 2}, find a Hamiltonian tour of minimum cost. In this paper, we provide an approximation algorithm for this problem achieving a performance guarantee of . This algorithm can be further improved obtaining a performance guarantee of . This is better than the one achieved by Papadimitriou and Yannakakis [8], with a ratio , more than a decade ago. We enhance their algorithm by an involved procedure and find an improved lower bound for the cost of an optimal Hamiltonian tour. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Supplemental Index |
| Externí odkaz: |
|
