{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:20:40Z","timestamp":1750306840546,"version":"3.41.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,3,17]],"date-time":"2014-03-17T00:00:00Z","timestamp":1395014400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2014,3,17]]},"abstract":"<jats:p>After two decades of progress in hardness of approximation we finally completely understand the extent to which many optimization problems can be approximated in polynomial time. Unfortunately, however, and despite significant efforts, many important problems continue to resist such an understanding. One example is the famous Traveling Salesman Problem, for which the best currently known hardness of approximation bounds are strongly believed to be quite far from the truth. In this article, we describe the main tools and techniques used in the currently best known approximation lower bounds for this problem. Among them are expander-like graph constructions called amplifiers and bounded-occurrence instances of standard constraint satisfaction problems. We also discuss how these ideas could be (modestly) improved, how (and whether) they may prove useful in eventually resolving the problem and what ingredients are still missing.<\/jats:p>","DOI":"10.1145\/2596583.2596599","type":"journal-article","created":{"date-parts":[[2014,3,24]],"date-time":"2014-03-24T13:45:50Z","timestamp":1395668750000},"page":"48-65","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Guest column"],"prefix":"10.1145","volume":"45","author":[{"given":"Michael","family":"Lampis","sequence":"first","affiliation":[{"name":"Kyoto University, Japan"}]}],"member":"320","published-online":{"date-parts":[[2014,3,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1017\/S096354839700299X"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_3_1","first-page":"379","volume-title":"SODA","author":"Asadpour Arash","year":"2010"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Piotr\n       \n      Berman\n     and \n      \n      \n      Marek\n       \n      Karpinski\n    .\n      \n  \n   \n  On some tighter inapproximability results (extended abstract). In Jir\u00ed Wiedermann Peter van Emde Boas and Mogens Nielsen editors ICALP volume \n  1644\n   of \n  Lecture Notes in Computer Science pages \n  200\n  --\n  209\n  . \n  Springer 1999\n  .   Piotr Berman and Marek Karpinski. On some tighter inapproximability results (extended abstract). In Jir\u00ed Wiedermann Peter van Emde Boas and Mogens Nielsen editors ICALP volume 1644 of Lecture Notes in Computer Science pages 200--209. Springer 1999.","DOI":"10.1007\/3-540-48523-6_17"},{"key":"e_1_2_1_5_1","unstructured":"Piotr Berman and Marek Karpinski. Efficient amplifiers and bounded degree optimization. Electronic Colloquium on Computational Complexity (ECCC) 8(53) 2001.  Piotr Berman and Marek Karpinski. Efficient amplifiers and bounded degree optimization. Electronic Colloquium on Computational Complexity (ECCC) 8(53) 2001."},{"key":"e_1_2_1_6_1","unstructured":"Piotr Berman and Marek Karpinski. Improved approximation lower bounds on small occurrence optimization. Electronic Colloquium on Computational Complexity (ECCC) 10(008) 2003.  Piotr Berman and Marek Karpinski. Improved approximation lower bounds on small occurrence optimization. Electronic Colloquium on Computational Complexity (ECCC) 10(008) 2003."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109627"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Hans-Joachim\n       \n      B\u00f6ckenhauer Juraj\n       \n      Hromkovic Ralf\n       \n      Klasing Sebastian\n       \n      Seibert and \n      \n      \n      Walter\n       \n      Unger\n    .\n      \n  \n   \n  An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequality. In Horst Reichel and Sophie Tison editors STACS volume \n  1770\n   of \n  Lecture Notes in Computer Science pages \n  382\n  --\n  394\n  . \n  Springer 2000\n  .   Hans-Joachim B\u00f6ckenhauer Juraj Hromkovic Ralf Klasing Sebastian Seibert and Walter Unger. An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequality. In Horst Reichel and Sophie Tison editors STACS volume 1770 of Lecture Notes in Computer Science pages 382--394. Springer 2000.","DOI":"10.1007\/3-540-46541-3_32"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Hans-Joachim B\u00f6ckenhauer and Sebastian Seibert. Improved lower bounds on the approximability of the traveling salesman problem. RAIRO - Theoretical Informatics and Applications 34:213--255 5 2000.  Hans-Joachim B\u00f6ckenhauer and Sebastian Seibert. Improved lower bounds on the approximability of the traveling salesman problem. RAIRO - Theoretical Informatics and Applications 34:213--255 5 2000.","DOI":"10.1051\/ita:2000115"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(88)80014-3"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432628"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.04.004"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.850116"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Miroslav\n       \n      Chleb\u00edk\n     and \n      \n      \n      Janka\n       \n      Chleb\u00edkov\u00e1\n    .\n      \n  \n   \n  Approximation hardness for small occurrence instances of NP-hard problems. In Rossella Petreschi Giuseppe Persiano and Riccardo Silvestri editors CIAC volume \n  2653\n   of \n  Lecture Notes in Computer Science pages \n  152\n  --\n  164\n  . \n  Springer 2003\n  .   Miroslav Chleb\u00edk and Janka Chleb\u00edkov\u00e1. Approximation hardness for small occurrence instances of NP-hard problems. In Rossella Petreschi Giuseppe Persiano and Riccardo Silvestri editors CIAC volume 2653 of Lecture Notes in Computer Science pages 152--164. Springer 2003.","DOI":"10.1007\/3-540-44849-7_21"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.07.003"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.06.046"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Nicos Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. 1976.  Nicos Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. 1976.","DOI":"10.1007\/978-94-011-7557-9_7"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.61"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2004.05.001"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-002-1001-6"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.12.001"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_23_1","unstructured":"Michael R. Garey and David S. Johnson. Computers and intractability: A guide to the theory of NP-completeness 1979.   Michael R. Garey and David S. Johnson. Computers and intractability: A guide to the theory of NP-completeness 1979."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.80"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756144"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00032-6"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0205-6"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Marek\n       \n      Karpinski Michael\n       \n      Lampis and \n      \n      \n      Richard\n       \n      Schmied\n    .\n      \n  \n   \n  New inapproximability bounds for TSP. In Leizhen Cai Siu-Wing Cheng and Tak Wah Lam editors ISAAC volume \n  8283\n   of \n  Lecture Notes in Computer Science pages \n  568\n  --\n  578\n  . \n  Springer 2013\n  .  Marek Karpinski Michael Lampis and Richard Schmied. New inapproximability bounds for TSP. In Leizhen Cai Siu-Wing Cheng and Tak Wah Lam editors ISAAC volume 8283 of Lecture Notes in Computer Science pages 568--578. Springer 2013.","DOI":"10.1007\/978-3-642-45030-3_53"},{"key":"e_1_2_1_31_1","unstructured":"Marek Karpinski and Richard Schmied. On Approximation Lower Bounds for TSP with Bounded Metrics. CoRR abs\/1201.5821 2012.  Marek Karpinski and Richard Schmied. On Approximation Lower Bounds for TSP with Bounded Metrics. CoRR abs\/1201.5821 2012."},{"key":"e_1_2_1_32_1","first-page":"27","volume-title":"Proc. 19th CATS","author":"Karpinski Marek","year":"2013"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Michael\n       \n      Lampis\n    .\n      \n  \n   \n  Improved Inapproximability for TSP. In Anupam Gupta Klaus Jansen Jos\u00e9 D. P. Rolim and Rocco A. Servedio editors APPROX-RANDOM volume \n  7408\n   of \n  Lecture Notes in Computer Science pages \n  243\n  --\n  253\n  . \n  Springer 2012\n  . (Journal version to appear in Theory of Computing).  Michael Lampis. Improved Inapproximability for TSP. In Anupam Gupta Klaus Jansen Jos\u00e9 D. P. Rolim and Rocco A. Servedio editors APPROX-RANDOM volume 7408 of Lecture Notes in Computer Science pages 243--253. Springer 2012. (Journal version to appear in Theory of Computing).","DOI":"10.1007\/978-3-642-32512-0_21"},{"key":"e_1_2_1_36_1","unstructured":"Michael Lampis. Local improvement gives better expanders. CoRR abs\/1211.0524 2012.  Michael Lampis. Local improvement gives better expanders. CoRR abs\/1211.0524 2012."},{"first-page":"560","volume-title":"Ostrovsky","author":"M\u00f6mke Tobias","key":"e_1_2_1_37_1"},{"key":"e_1_2_1_38_1","series-title":"LIPIcs","first-page":"30","volume-title":"Christoph D\u00fcrr and Thomas Wilke","author":"Mucha Marcin","year":"2012"},{"volume-title":"IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011","year":"2011","author":"Ostrovsky Rafail","key":"e_1_2_1_39_1"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0008-z"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.18.1.1"},{"key":"e_1_2_1_43_1","unstructured":"Andr\u00e1s Seb\u00f6 and Jens Vygen. 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. (to appear in Combinatorica) CoRR abs\/1201.1870 2012.  Andr\u00e1s Seb\u00f6 and Jens Vygen. 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. (to appear in Combinatorica) CoRR abs\/1201.1870 2012."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380839"},{"volume-title":"Electronic Colloquium on Computational Complexity (ECCC)","year":"2010","author":"Trevisan Luca","key":"e_1_2_1_45_1"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2596583.2596599","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2596583.2596599","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:04Z","timestamp":1750234204000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2596583.2596599"}},"subtitle":["the elusive inapproximability of the TSP"],"short-title":[],"issued":{"date-parts":[[2014,3,17]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,3,17]]}},"alternative-id":["10.1145\/2596583.2596599"],"URL":"https:\/\/doi.org\/10.1145\/2596583.2596599","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2014,3,17]]},"assertion":[{"value":"2014-03-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}