arXiv:2007.01409cs.DS2020-07-02

A (Slightly) Improved Approximation Algorithm for Metric TSP

Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan

Abstract

For some $ε> 10^{-36}$ we give a randomized $3/2-ε$ approximation algorithm for metric TSP.

arXiv comments
Journal reference
DOI
Subjects: cs.DSData Structures and Algorithms math.COCombinatorics math.PRProbability

On Hacker News

Linked by 4 identifiable commenters in 4 comments across 1 thread, from Oct 2020 to Oct 2020.

Comments linking this paper, per year.

Discussed in comments1 thread

Computer Scientists Break Traveling Salesperson Record Oct 20204 comments
- Oh man, it's actually a real improvement! I was afraid it was more pop sci, but not this is pretty cool. I think this is the paper? https://arxiv.org/abs/2007.01409
  
  Tyr42Oct 8, 2020View on HN Parent context
- The paper is really nicely written: https://arxiv.org/abs/2007.01409 It's lengthy and full of some quite technical sections, but those are interspersed with sections sketching the high-level intuition and proving more informal versions of the technical theorems in simplified…
  
  mjnOct 8, 2020View on HN Parent context
- “The algorithm we study is very similar, except we choose a random spanning tree based on the standard linear programming relaxation of TSP.” That’s so subtle to suggest but incredible hard to prove https://arxiv.org/abs/2007.01409
  
  fmeyerOct 8, 2020View on HN Parent context
- The original paper mentioned in the article [1] deals with metric TSP, so a triangle inequality must be satisfied. This means that you can actually find a space where the points will be the coordinates. Anyway, the grandparent solves the Euclidean TSP which is still an…
  
  mousebaikerOct 9, 2020View on HN Parent context

Submitted to Hacker News

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