×

Improved inapproximability for TSP. (English) Zbl 1366.68077

Summary: The Traveling Salesman Problem is one of the most studied problems in the theory of algorithms and its approximability is a long-standing open question. Prior to the present work, the best known inapproximability threshold was \(\frac{220}{219}\), due to C. H. Papadimitriou and S. Vempala [Combinatorica 26, No. 1, 101–120 (2006; Zbl 1106.90071)]. Here, using an essentially different construction and also relying on the work of Berman and Karpinski on bounded-occurrence CSPs, we give an alternative and simpler inapproximability proof which improves the bound to \(\frac{185}{184}\).

MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
90C27 Combinatorial optimization

Citations:

Zbl 1106.90071
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] [1] PIOTRBERMAN ANDMAREKKARPINSKI: On some tighter inapproximability results (extended abstract). In Proc. 26th Internat. Colloq. on Automata, Languages and Programming (ICALP’99), volume 1644 of LNCS, pp. 200–209. Springer, 1999. [doi:10.1007/3-540-48523-6_17]218,220
[2] [2] PIOTRBERMAN ANDMAREKKARPINSKI: Efficient amplifiers and bounded degree optimization. Electron. Colloq. on Comput. Complexity (ECCC), 8(53), 2001.ECCC.218,220
[3] [3] PIOTRBERMAN ANDMAREKKARPINSKI: Improved approximation lower bounds on small occurrence optimization. Electron. Colloq. on Comput. Complexity (ECCC), 10(8), 2003.ECCC. 218,220,221,224,225,234
[4] [4] HANS-JOACHIMBÖCKENHAUER, JURAJHROMKOVI \check{}C, RALFKLASING, SEBASTIANSEIBERT, ANDWALTERUNGER: An improved lower bound on the approximability of metric TSP and approximation algorithms for the TSP with sharpened triangle inequality. In Proc. 17th Ann. Symp. on Theoretical Aspects of Comp. Sci. (STACS’00), volume 1770 of LNCS, pp. 382–394. Springer, 2000. [doi:10.1007/3-540-46541-3_32]218
[5] [5] NICOSCHRISTOFIDES: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, Carnegie-Mellon University, 1976.217
[6] [6] LARSENGEBRETSEN: An explicit lower bound for TSP with distances one and two. Algorithmica, 35(4):301–319, 2003. Preliminary version inSTACS’99. [doi:10.1007/s00453-002-1001-6]218
[7] [7] LARSENGEBRETSEN ANDMAREKKARPINSKI: TSP with bounded metrics. J. Comput. System Sci., 72(4):509–546, 2006. Preliminary version inICALP’01. [doi:10.1016/j.jcss.2005.12.001]218
[8] [8] SHAYANOVEISGHARAN, AMINSABERI,ANDMOHITSINGH: A randomized rounding approach to the traveling salesman problem. In Proc. 52nd FOCS, pp. 550–559. IEEE Comp. Soc. Press, 2011. [doi:10.1109/FOCS.2011.80]217
[9] [9] JOHANHÅSTAD: Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001. Preliminary version inSTOC’97. [doi:10.1145/502090.502098]218,220
[10] [10] MAREKKARPINSKI, MICHAELLAMPIS,ANDRICHARDSCHMIED: New inapproximability bounds for TSP. In Proc. 24th Internat. Symp. on Symbolic and Algebraic Computation (ISAAC’13), volume 8283 of LNCS, pp. 568–578. Springer, 2013. See also atECCC. [doi:10.1007/978-3-64245030-3_53]219,234
[11] [11] MAREKKARPINSKI ANDRICHARDSCHMIED: On approximation lower bounds for TSP with bounded metrics. Electron. Colloq. on Comput. Complexity (ECCC), 19(8), 2012.ECCC. See also atarXiv.218
[12] [12] MICHAELLAMPIS: Improved inapproximability for TSP. In Proc. 15th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’12), volume 1770 THEORY OFCOMPUTING, Volume 10 (9), 2014, pp. 217–236235 MICHAELLAMPIS of LNCS, pp. 243–253. Springer, 2012. See also atarXiv. [doi:10.1007/978-3-642-32512-0_21] 217
[13] [13] TOBIASMÖMKE ANDOLASVENSSON: Approximating graphic TSP by matchings. Technical report, 2011. Preliminary version inFOCS’11. [arXiv:1104.3090]217
[14] [14] MARCINMUCHA:139-approximation for graphic TSP. Theory Comput. Syst., 2012. Preliminary version inSTACS’12. [doi:10.1007/s00224-012-9439-7]217
[15] [15] CHRISTOSH. PAPADIMITRIOU ANDSANTOSHVEMPALA: On the approximability of the traveling salesman problem (extended abstract). In Proc. 32nd STOC, pp. 126–133. ACM Press, 2000. [doi:10.1145/335305.335320]218
[16] [16] CHRISTOSH. PAPADIMITRIOU ANDSANTOSHVEMPALA: On the approximability of the traveling salesman problem. Combinatorica, 26(1):101–120, 2006. Preliminary version inSTOC’00. [doi:10.1007/s00493-006-0008-z]218,219,234
[17] [17] CHRISTOSH. PAPADIMITRIOU ANDMIHALISYANNAKAKIS: The traveling salesman problem with distances one and two. Math. Oper. Res., 18(1):1–11, 1993. [doi:10.1287/moor.18.1.1]218
[18] [18] ANDRÁSSEB ˝O ANDJENSVYGEN: Shorter tours by nicer ears: 7/5-approximation for graphic TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Technical report, 2012. To appear in Combinatorica. [arXiv:1201.1870]217 AUTHOR Michael Lampis KTH Royal Institute of Technology mlampiskth se http://www.csc.kth.se/ mlampis ABOUT THE AUTHOR MICHAELLAMPISreceived his Ph. D. from theCity University of New Yorkin 2011 advised byAmotz Bar-Noy. His favorite research area is parameterized complexity, but it is not hard to get him interested in other branches of theoretical computer science. The two procrastination activities he most excels in are reading theNew York Timesand playing blitz chess matchesonline. When he grows up he wants to be a computer science professor or an astronaut. THEORY OFCOMPUTING, Volume 10 (9), 2014, pp. 217–236236
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.