Improved lower bounds on the approximability of the traveling salesman problem

 Access to full text

 Full (PDF)

1. [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. [2] S. Arora, Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and Other Geometrie Problems. J. ACM 45 (1998) 753-782. Zbl1064.90566MR1668147
3. [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. [4] S. Arora and C. Lund, Hardness of Approximations, Chapter 10 of [12], pp. 399-446. 
5. [5] M. A. Bender and C. Chekuri, Performance guarantees for the TSP with a parameterized triangle inequality. Inform. Process. Lett. 73 (2000) 17-21. MR1741501
6. [6] 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 (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) 7286. (Full version in: Electronic Colloquium on Computational Complexity (http://www.eccc.uni-trier.de/eccc/), Report No. 31 (1999).) Zbl0961.68058
7. [7] 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 (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. Zbl1028.90044MR1781748
8. [8] H.-J. Böckenhauer, J. Hromkovič, R. Klasing, S. Seibert and W. Unger, Approximation Algorithms for the TSP with Sharpened Triangle Inequality. Inform. Process. Lett. 75 (2000) 133-138. Zbl1028.90044MR1776665
9. [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. [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. [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.unitrier.de/eccc/), Revision 1 of Report No, 46 (1999). MR1734066
12. [12] D. S. Hochbaum, Approximation Algorithms for NP-hard Problems. PWS Publishing Company (1996). Zbl05899342
13. [13] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan and D. B. Shmoys, The Traveling Salesman Problem. John Wiley & Sons (1985). Zbl0562.00014MR811467
14. [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). Zbl0940.68062
15. [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). Zbl1043.68579MR1640479
16. [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). Zbl1296.68083MR2114525
17. [17] Ch. Papadimitriou and M. Yannakakis, The traveling salesman problem with distances one and two. Math. Oper. Res. 18 (1993) 1-11. Zbl0778.90057MR1250103