2 papers
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.DS2021
A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP
Anna Karlin, Nathan Klein, Shayan Oveis Gharan
We show that for some and any metric TSP instance, the max entropy algorithm returns a solution of expected cost at most times the cost of the optimal…