Abstract
In this paper, we study the approximability of the metric Traveling Salesman Problem (TSP) and prove new explicit inapproximability bounds for that problem. The best up to now known hardness of approximation bounds were 185/184 for the symmetric case (due to Lampis) and 117/116 for the asymmetric case (due to Papadimitriou and Vempala). We construct here two new bounded occurrence CSP reductions which improve these bounds to 123/122 and 75/74, respectively. The latter bound is the first improvement in more than a decade for the case of the asymmetric TSP. One of our main tools, which may be of independent interest, is a new construction of a bounded degree wheel amplifier used in the proof of our results.
The full version of the paper is to be found under: http://arxiv.org/abs/1303.6437
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof Verification and the Hardness of Approximation Problems. J. ACM 45, 501–555 (1998)
Asadpour, A., Goemans, M., Madry, A., Oveis Gharan, S., Saberi, A.: An O(logn/ loglogn)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem. In: Proc. 21st SODA 2010, pp. 379–389 (2010)
Berman, P., Karpinski, M.: On Some Tighter Inapproximability Results. In: Wiedermann, J., Van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 200–209. Springer, Heidelberg (1999)
Berman, P., Karpinski, M.: Efficient Amplifiers and Bounded Degree Optimization, ECCC TR01-053 (2001)
Berman, P., Karpinski, M.: Improved Approximation Lower Bounds on Small Occurrence Optimization, ECCC TR03-008 (2003)
Berman, P., Karpinski, M.: 8/7-approximation algorithm for (1, 2)-TSP. In: Proc. 17th SODA 2006, pp. 641–648 (2006)
Bläser, M.: A 3/4-Approximation Algorithm for Maximum ATSP with Weights Zero and One. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) RANDOM 2004 and APPROX 2004. LNCS, vol. 3122, pp. 61–71. Springer, Heidelberg (2004)
Böckenhauer, H.-J., Seibert, S.: Improved Lower Bounds on the Approximability of the Traveling Salesman Problem. Theor. Inform. Appl. 34, 213–255 (2000)
Christofides, N.: Worst-Case Analysis of a New Heuristic for the Traveling Salesman Problem, Technical Report CS-93-13, Carnegie Mellon University, Pittsburgh (1976)
Engebretsen, L.: An Explicit Lower Bound for TSP with Distances One and Two. Algorithmica 35, 301–318 (2003)
Engebretsen, L., Karpinski, M.: TSP with Bounded Metrics. J. Comput. Syst. Sci. 72, 509–546 (2006)
Håstad, J.: Some Optimal Inapproximability Results. J. ACM 48, 798–859 (2001)
Karpinski, M., Schmied, R.: On Approximation Lower Bounds for TSP with Bounded Metrics, CoRR arXiv: abs/1201.5821 (2012)
Karpinski, M., Schmied, R.: On Improved Inapproximability Results for the Shortest Superstring and Related Problems. In: Proc. 19th CATS 2013. CRPIT, vol. 141, pp. 27–36 (2013)
Lampis, M.: Improved Inapproximability for TSP. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) APPROX 2012 and RANDOM 2012. LNCS, vol. 7408, pp. 243–253. Springer, Heidelberg (2012)
Mömke, T., Svensson, O.: Approximating Graphic TSP by Matchings. In: Proc. IEEE 52nd FOCS 2011, pp. 560–569 (2011)
Mucha, M.: 13/9-Approximation for Graphic TSP. In: Proc. STACS 2012, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. LIPIcs, vol. 14, pp. 30–41 (2012)
Oveis Gharan, S., Saberi, A., Singh, M.: A Randomized Rounding Approach to the Traveling Salesman Problem. In: Proc. IEEE 52nd FOCS 2011, pp. 550–559 (2011)
Papadimitriou, C., Vempala, S.: On the Approximability of the Traveling Salesman Problem. In: Proc. 32nd ACM STOC 2000, pp. 126–133 (2000); see also a corrected version in Combinatorica 26, 101–120 (2006)
Papadimitriou, C., Yannakakis, M.: The Traveling Salesman Problem with Distances One and Two. Math. Oper. Res. 18, 1–11 (1993)
Sebö, A., Vygen, J.: Shorter Tours by Nicer Ears, CoRR arXiv: abs/1201.1870 (2012); to appear in Combinatorica
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Karpinski, M., Lampis, M., Schmied, R. (2013). New Inapproximability Bounds for TSP. In: Cai, L., Cheng, SW., Lam, TW. (eds) Algorithms and Computation. ISAAC 2013. Lecture Notes in Computer Science, vol 8283. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45030-3_53
Download citation
DOI: https://doi.org/10.1007/978-3-642-45030-3_53
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45029-7
Online ISBN: 978-3-642-45030-3
eBook Packages: Computer ScienceComputer Science (R0)