Improved Lower Bounds on the Approximability of the Traveling Salesman Problem

Hans-Joachim Böckenhauer; Sebastian Seibert

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 34, Issue: 3, page 213-255
  • ISSN: 0988-3754

Abstract

top
This paper deals with lower bounds on the approximability of different subproblems of the Traveling Salesman Problem (TSP) which is known not to admit any polynomial time approximation algorithm in general (unless 𝒫 = 𝒩𝒫 ). First of all, we present an improved lower bound for the Traveling Salesman Problem with Triangle Inequality, Delta-TSP for short. Moreover our technique, an extension of the method of Engebretsen [11], also applies to the case of relaxed and sharpened triangle inequality, respectively, denoted Δ β -TSP for an appropriate β. In case of the Delta-TSP, we obtain a lower bound of 3813 3812 - ε on the polynomial-time approximability (for any small ε > 0 ), compared to the previous bound of 5381 5380 - ε in [11]. In case of the Δ β -TSP, for the relaxed case ( β > 1 ) we present a lower bound of 3803 + 10 β 3804 + 8 β - ε , and for the sharpened triangle inequality ( 1 2 < β < 1 ), the lower bound is 7611 + 10 β 2 + 5 β 7612 + 8 β 2 + 4 β - ε . The latter result is of interest especially since it shows that the TSP is 𝒜𝒫𝒳 -hard even if one comes arbitrarily close to the trivial case that all edges have the same cost.

How to cite

top

Böckenhauer, Hans-Joachim, and Seibert, Sebastian. "Improved Lower Bounds on the Approximability of the Traveling Salesman Problem." RAIRO - Theoretical Informatics and Applications 34.3 (2010): 213-255. <http://eudml.org/doc/222088>.

@article{Böckenhauer2010,
abstract = { This paper deals with lower bounds on the approximability of different subproblems of the Traveling Salesman Problem (TSP) which is known not to admit any polynomial time approximation algorithm in general (unless $\mathcal\{P\}=\mathcal\{NP\}$). First of all, we present an improved lower bound for the Traveling Salesman Problem with Triangle Inequality, Delta-TSP for short. Moreover our technique, an extension of the method of Engebretsen [11], also applies to the case of relaxed and sharpened triangle inequality, respectively, denoted $\Delta_\beta$-TSP for an appropriate β. In case of the Delta-TSP, we obtain a lower bound of $\frac\{3813\}\{3812\}-\varepsilon$ on the polynomial-time approximability (for any small $\varepsilon> 0$), compared to the previous bound of $\frac\{5381\}\{5380\}-\varepsilon$ in [11]. In case of the $\Delta_\beta$-TSP, for the relaxed case ($\beta> 1$) we present a lower bound of $\frac\{3803+10\beta\}\{3804+8\beta\}-\varepsilon$, and for the sharpened triangle inequality ($\frac\{1\}\{2\}< \beta< 1$), the lower bound is $\frac\{7611+10\beta^2+5\beta\}\{7612+8\beta^2+4\beta\}-\varepsilon$. The latter result is of interest especially since it shows that the TSP is $\mathcal\{APX\}$-hard even if one comes arbitrarily close to the trivial case that all edges have the same cost. },
author = {Böckenhauer, Hans-Joachim, Seibert, Sebastian},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Approximation algorithms; Traveling Salesman Problem.; traveling salesman problem},
language = {eng},
month = {3},
number = {3},
pages = {213-255},
publisher = {EDP Sciences},
title = {Improved Lower Bounds on the Approximability of the Traveling Salesman Problem},
url = {http://eudml.org/doc/222088},
volume = {34},
year = {2010},
}

TY - JOUR
AU - Böckenhauer, Hans-Joachim
AU - Seibert, Sebastian
TI - Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 34
IS - 3
SP - 213
EP - 255
AB - This paper deals with lower bounds on the approximability of different subproblems of the Traveling Salesman Problem (TSP) which is known not to admit any polynomial time approximation algorithm in general (unless $\mathcal{P}=\mathcal{NP}$). First of all, we present an improved lower bound for the Traveling Salesman Problem with Triangle Inequality, Delta-TSP for short. Moreover our technique, an extension of the method of Engebretsen [11], also applies to the case of relaxed and sharpened triangle inequality, respectively, denoted $\Delta_\beta$-TSP for an appropriate β. In case of the Delta-TSP, we obtain a lower bound of $\frac{3813}{3812}-\varepsilon$ on the polynomial-time approximability (for any small $\varepsilon> 0$), compared to the previous bound of $\frac{5381}{5380}-\varepsilon$ in [11]. In case of the $\Delta_\beta$-TSP, for the relaxed case ($\beta> 1$) we present a lower bound of $\frac{3803+10\beta}{3804+8\beta}-\varepsilon$, and for the sharpened triangle inequality ($\frac{1}{2}< \beta< 1$), the lower bound is $\frac{7611+10\beta^2+5\beta}{7612+8\beta^2+4\beta}-\varepsilon$. The latter result is of interest especially since it shows that the TSP is $\mathcal{APX}$-hard even if one comes arbitrarily close to the trivial case that all edges have the same cost.
LA - eng
KW - Approximation algorithms; Traveling Salesman Problem.; traveling salesman problem
UR - http://eudml.org/doc/222088
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. S. Arora, Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and Other Geometric Problems. J. ACM45 (1998) 753-782.  
  3. S. Arora, Nearly linear time approximation schemes for Euclidean TSP and other geometric problems, in Proc. 38th Ann. Symp. on Foundations of Comp. Sci. (FOCS '97), IEEE (1997) 554-563.  
  4. S. Arora and C. Lund, Hardness of Approximations, Chapter 10 of [], pp. 399-446.  
  5. M.A. Bender and C. Chekuri, Performance guarantees for the TSP with a parameterized triangle inequality. Inform. Process. Lett.73 (2000) 17-21.  
  6. 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 (Extended Abstract), edited by G.C. Bongiovanni, G. Gambosi and R. Petreschi, Algorithms and Complexity, Proc. 4th Italian Conference CIAC 2000. Springer, Lecture Notes in Comput. Sci.1767 (2000) 72-86. (Full version in: Electronic Colloquium on Computational Complexity (http://www.eccc.uni-trier.de/eccc/), Report No. 31 (1999).)  
  7. 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 (Extended Abstract), edited by H. Reichel and S. Tison, STACS 2000, Proc. 17th Ann. Symp. on Theoretical Aspects of Comp. Sci., Springer, Lecture Notes in Comput. Sci.1770 (2000) 382-394.  
  8. H.-J. Böckenhauer, J. Hromkovic, R. Klasing, S. Seibert and W. Unger, Approximation Algorithms for the TSP with Sharpened Triangle Inequality. Inform. Process. Lett.75 (2000) 133-138.  
  9. P. Berman and M. Karpinski, On some tighter inapproximability results. Technical Report TR98-029, Electronic Colloquium on Computational Complexity (1998) http://www.eccc.uni-trier.de/eccc/  
  10. 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).  
  11. L. Engebretsen, An explicit lower bound for TSP with distances one and two. Extended abstract, edited by C. Meinel and S. Tison, STACS 99, Proc. 16th Ann. Symp. on Theoretical Aspects of Comp. Sci. Springer, Lecture Notes in Comput. Sci.1563 (1999) 373-382. Full version in: Electronic Colloquium on Computational Complexity (http://www.eccc.uni-trier.de/eccc/), Revision 1 of Report No. 46 (1999).  
  12. D.S. Hochbaum, Approximation Algorithms for NP-hard Problems. PWS Publishing Company (1996).  
  13. E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, The Traveling Salesman Problem. John Wiley & Sons (1985).  
  14. I.S.B. Mitchell, Guillotine subdivisions approximate polygonal subdivisions: Part II - a simple polynomial-time approximation scheme for geometric k-MST, TSP and related problems. Technical Report, Dept. of Applied Mathematics and Statistics, Stony Brook (1996).  
  15. E.W. Mayr, H.J. Prömel and A. Steger, Lectures on Proof Verification and Approximation Algorithms. Springer, Lecture Notes in Comput. Sci.1967 (1998).  
  16. Ch. Papadimitriou and S. Vempala, On the approximability of the traveling salesman problem, in Proc. 32nd Ann. Symp. on Theory of Comp. (STOC '00), ACM (2000).  
  17. Ch. 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.