3 citations · 5 across the 7 of their papers we have counts for
Showing 2022Show all
2 papers · 1 filter
cs.DS2022
A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
We show that the max entropy algorithm can be derandomized (with respect to a particular objective function) to give a deterministic approximation algorithm for metric TSP…
cs.DS2022
A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP
Billy Jin, Nathan Klein, David P. Williamson
A long-standing conjecture for the traveling salesman problem (TSP) states that the integrality gap of the standard linear programming relaxation of the TSP is at most 4/3. Despite…