Approximation algorithms for the traveling salesman problem with range condition
Arun Kumar, D. ; Pandu Rangan, C.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000), p. 173-181 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 2000-01-01
@article{ITA_2000__34_3_173_0,
     author = {Arun Kumar, D. and Pandu Rangan, C.},
     title = {Approximation algorithms for the traveling salesman problem with range condition},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {34},
     year = {2000},
     pages = {173-181},
     mrnumber = {1796267},
     zbl = {0970.68196},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2000__34_3_173_0}
}

Arun Kumar, D.; Pandu Rangan, C. Approximation algorithms for the traveling salesman problem with range condition. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000) pp. 173-181. http://gdmltest.u-ga.fr/item/ITA_2000__34_3_173_0/

[1] T. Andreae and H.-J. Bandelt, Performance guarantees for approximation algorithms depending on parametrized triangle inequalities. SIAM J. Discrete Math. 8 (1995) 1-16. | MR 1315955 | Zbl 0832.90089

[2] M. A. Bender and C. Chekuri, Performance guarantees for the TSP with a parametrized triangle inequality, in Proc. WADS'99. Springer, Lecture Notes in Comput. Sci. 1663 (1999) 80-85. | MR 1734094 | Zbl 1063.68700

[3] H.-J. Böckenhauer, J. Hromkovič, R. Klasing, S. Seibert and W. Unger, An improved lower bound on the approximability of metric TSP and approximation algorithms for the TSP with sharpened triangle Inequality, in Proc. STACS 2000. Springer, Lecture Notes in Comput. Sci. (to appear). | MR 1776665 | Zbl 1028.90044

[4] H.-J. Böckenhauer, J. Hromkovič, R. Klasing, S. Seibert and W. Unger, Towards the Notion of Stability of Approximation Algorithms and the Traveling Salesman Problem, in Electronic Colloquium on Computational Complexity. Report No. 31 (1999).

[5] N. Christofides, Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report 388, Graduate School of Industrial Administration. Carnegie-Mellon University, Pittsburgh (1976).

[6] J. Edmonds and E. L. Johnson, Matching: A well-solved class of integer linear programs, in Proc. Calgary International conference on Combinatorial Structures and Their Applications. Gordon and Breach (1970) 88-92. | MR 267898 | Zbl 0258.90032

[7] M. R. Garey, R. L. Graham and D. J. Johnson, Some NP-cornplete geometric problems, in Proc. ACM Symposium on Theory of Computing (1976) 10-22. | Zbl 0377.68036

[8] H. N. Gabow and R. E. Tarjan, Faster scaling algorithms for general graph-matching problems. J. ACM 28 (1991) 815-853. | MR 1134518 | Zbl 0799.68145

[9] J. Hromkovič, Stability of approximation algorithms for hard optimisation problems, in Proc. SOFSEM'99. Springer-Verlag, Lecture Notes in Comput. Sci. 1725 (1999) 29-46. | MR 1784516 | Zbl 0961.65060

[10] J. Hromkovič, Stability of approximation algorithms and the knapsack problem, in Jewels are forever, edited by J. Karhumäki, H. Maurer and G. Rozenberg. Springer-Verlag (1999) 238-249. | MR 1719081 | Zbl 0945.68074

[11] C. H. Papadimitriou, Euclidean TSP is NP-complete. TCS 4 (1977) 237-244. | MR 455550 | Zbl 0386.90057

[12] C. H. Papadimitriou and M. Yannakakis, The Traveling salesman problem with distances one and two. Math. Oper. Res. 18 (1993) 1-11. | MR 1250103 | Zbl 0778.90057