TY - GEN

T1 - Approximating the held-karp bound for metric TSP in nearly-linear time

AU - Chekuri, Chandra

AU - Quanrud, Kent

N1 - Publisher Copyright:
© 2017 IEEE.

PY - 2017/11/10

Y1 - 2017/11/10

N2 - We give a nearly linear-time randomized approximation scheme for the Held-Karp bound [22] for Metric-TSP. Formally, given an undirected edge-weighted graph G = (V,E) on m edges and ϵ 0, the algorithm outputs in O(m log^4 n/ϵ^2) time, with high probability, a (1 + ϵ)-approximation to the Held-Karp bound on the Metric-TSP instance induced by the shortest path metric on G. The algorithm can also be used to output a corresponding solution to the Subtour Elimination LP. We substantially improve upon the O(m^2 log^2(m)/ϵ^2) running time achieved previously by Garg and Khandekar.

AB - We give a nearly linear-time randomized approximation scheme for the Held-Karp bound [22] for Metric-TSP. Formally, given an undirected edge-weighted graph G = (V,E) on m edges and ϵ 0, the algorithm outputs in O(m log^4 n/ϵ^2) time, with high probability, a (1 + ϵ)-approximation to the Held-Karp bound on the Metric-TSP instance induced by the shortest path metric on G. The algorithm can also be used to output a corresponding solution to the Subtour Elimination LP. We substantially improve upon the O(m^2 log^2(m)/ϵ^2) running time achieved previously by Garg and Khandekar.

UR - http://www.scopus.com/inward/record.url?scp=85041104968&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85041104968&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2017.78

DO - 10.1109/FOCS.2017.78

M3 - Conference contribution

AN - SCOPUS:85041104968

T3 - Annual Symposium on Foundations of Computer Science - Proceedings

SP - 789

EP - 800

BT - Proceedings - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017

PB - IEEE Computer Society

T2 - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017

Y2 - 15 October 2017 through 17 October 2017

ER -