# Approximation algorithms for the traveling salesman problem with range condition

D. Arun Kumar; C. Pandu Rangan

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2000)

- Volume: 34, Issue: 3, page 173-181
- ISSN: 0988-3754

## Access Full Article

top## How to cite

topArun Kumar, D., and Pandu Rangan, C.. "Approximation algorithms for the traveling salesman problem with range condition." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 34.3 (2000): 173-181. <http://eudml.org/doc/92631>.

@article{ArunKumar2000,

author = {Arun Kumar, D., Pandu Rangan, C.},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {odd degree restricted graphs},

language = {eng},

number = {3},

pages = {173-181},

publisher = {EDP-Sciences},

title = {Approximation algorithms for the traveling salesman problem with range condition},

url = {http://eudml.org/doc/92631},

volume = {34},

year = {2000},

}

TY - JOUR

AU - Arun Kumar, D.

AU - Pandu Rangan, C.

TI - Approximation algorithms for the traveling salesman problem with range condition

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 2000

PB - EDP-Sciences

VL - 34

IS - 3

SP - 173

EP - 181

LA - eng

KW - odd degree restricted graphs

UR - http://eudml.org/doc/92631

ER -

## References

top- [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. Zbl0832.90089MR1315955
- [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. Zbl1063.68700MR1734094
- [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). Zbl1028.90044MR1776665
- [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). Zbl1094.90036
- [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. Zbl0258.90032MR267898
- [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. Zbl0377.68036
- [8] H. N. Gabow and R. E. Tarjan, Faster scaling algorithms for general graph-matching problems. J. ACM 28 (1991) 815-853. Zbl0799.68145MR1134518
- [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. Zbl0961.65060MR1784516
- [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. Zbl0945.68074MR1719081
- [11] C. H. Papadimitriou, Euclidean TSP is NP-complete. TCS 4 (1977) 237-244. Zbl0386.90057MR455550
- [12] C. H. Papadimitriou and M. Yannakakis, The Traveling salesman problem with distances one and two. Math. Oper. Res. 18 (1993) 1-11. Zbl0778.90057MR1250103

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.