Approximation Algorithms for the Traveling Salesman Problem with Range Condition

D. Arun Kumar; C. Pandu Rangan

RAIRO - Theoretical Informatics and Applications (2010)

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

Abstract

top
We prove that the Christofides algorithm gives a 4 3 approximation ratio for the special case of traveling salesman problem (TSP) in which the maximum weight in the given graph is at most twice the minimum weight for the odd degree restricted graphs. A graph is odd degree restricted if the number of odd degree vertices in any minimum spanning tree of the given graph is less than 1 4 times the number of vertices in the graph. We prove that the Christofides algorithm is more efficient (in terms of runtime) than the previous existing algorithms for this special case of the traveling salesman problem. Secondly, we apply the concept of stability of approximation to this special case of traveling salesman problem in order to partition the set of all instances of TSP into an infinite spectrum of classes according to their approximability.

How to cite

top

D. Arun Kumar, and Pandu Rangan, C.. " Approximation Algorithms for the Traveling Salesman Problem with Range Condition." RAIRO - Theoretical Informatics and Applications 34.3 (2010): 173-181. <http://eudml.org/doc/221984>.

@article{D2010,
abstract = { We prove that the Christofides algorithm gives a $\frac\{4\}\{3\}$ approximation ratio for the special case of traveling salesman problem (TSP) in which the maximum weight in the given graph is at most twice the minimum weight for the odd degree restricted graphs. A graph is odd degree restricted if the number of odd degree vertices in any minimum spanning tree of the given graph is less than $\frac\{1\}\{4\}$ times the number of vertices in the graph. We prove that the Christofides algorithm is more efficient (in terms of runtime) than the previous existing algorithms for this special case of the traveling salesman problem. Secondly, we apply the concept of stability of approximation to this special case of traveling salesman problem in order to partition the set of all instances of TSP into an infinite spectrum of classes according to their approximability. },
author = {D. Arun Kumar, Pandu Rangan, C.},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {odd degree restricted graphs},
language = {eng},
month = {3},
number = {3},
pages = {173-181},
publisher = {EDP Sciences},
title = { Approximation Algorithms for the Traveling Salesman Problem with Range Condition},
url = {http://eudml.org/doc/221984},
volume = {34},
year = {2010},
}

TY - JOUR
AU - D. Arun Kumar
AU - Pandu Rangan, C.
TI - Approximation Algorithms for the Traveling Salesman Problem with Range Condition
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 34
IS - 3
SP - 173
EP - 181
AB - We prove that the Christofides algorithm gives a $\frac{4}{3}$ approximation ratio for the special case of traveling salesman problem (TSP) in which the maximum weight in the given graph is at most twice the minimum weight for the odd degree restricted graphs. A graph is odd degree restricted if the number of odd degree vertices in any minimum spanning tree of the given graph is less than $\frac{1}{4}$ times the number of vertices in the graph. We prove that the Christofides algorithm is more efficient (in terms of runtime) than the previous existing algorithms for this special case of the traveling salesman problem. Secondly, we apply the concept of stability of approximation to this special case of traveling salesman problem in order to partition the set of all instances of TSP into an infinite spectrum of classes according to their approximability.
LA - eng
KW - odd degree restricted graphs
UR - http://eudml.org/doc/221984
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.  
  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.  
  3. H.-J. Böckenhauer, J. Hromkovic, 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).  
  4. H.-J. Böckenhauer, J. Hromkovic, 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.  
  7. M.R. Garey, R.L. Graham and D.J. Johnson, Some NP-complete geometric problems, in Proc. ACM Symposium on Theory of Computing (1976) 10-22.  
  8. H.N. Gabow and R.E. Tarjan, Faster scaling algorithms for general graph-matching problems. J. ACM28 (1991) 815-853.  
  9. J. Hromkovic, Stability of approximation algorithms for hard optimisation problems, in Proc. SOFSEM'99. Springer-Verlag, Lecture Notes in Comput. Sci.1725 (1999) 29-46.  
  10. J. Hromkovic, 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.  
  11. C.H. Papadimitriou, Euclidean TSP is NP-complete. TCS4 (1977) 237-244.  
  12. C.H. Papadimitriou and M. Yannakakis, The Traveling salesman problem with distances one and two. Math. Oper. Res.18 (1993) 1-11.  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.