STOC 2021

A (slightly) improved approximation algorithm for metric TSP

Conference Paper Best Papers Algorithms and Complexity · Theoretical Computer Science

Abstract

For some > 10 −36 we give a randomized 3/2− approximation algorithm for metric TSP.

Authors

Keywords

Approximation Algorithms
Max Entropy
Near Minimum Cuts
Randomized Rounding
Strongly Rayleigh
Traveling Salesperson Problem

Context

Venue: ACM Symposium on Theory of Computing
Archive span: 1969-2025
Indexed papers: 4364
Paper id: 415084142734353888