Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time.
Chandra ChekuriKent QuanrudPublished in: FOCS (2017)
Keyphrases
- worst case
- traveling salesman problem
- upper bound
- lower bound
- metric space
- np hard
- search space
- invited talk
- similarity metric
- error bounds
- ant colony optimization
- travelling salesman
- np hard problems
- case study
- distance function
- distance measure
- shortest path
- triangle inequality
- optimization problems
- satisfy the triangle inequality