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 -