HackerPapers

arXiv:1303.6437cs.CC

New Inapproximability Bounds for TSP

Marek Karpinski, Michael Lampis, Richard Schmied

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

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.

arXiv comments
Journal reference
DOI
Subjects
cs.CCComputational Complexity cs.DMDiscrete Mathematics cs.DSData Structures and Algorithms math.COCombinatorics math.OCOptimization and Control

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Feb 2018 to Feb 2018.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Likelihood of discontinuous progress around the development of AGI 1 comment

    • For traveling salesmen problem there is Christofides algorithm which gives result that is no longer than 3/2 of optimal one. Theoretical bound on inapproximability of symmetrical TSP currently is 185/184. https://arxiv.org/abs/1303.6437

      red75primeView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.