71 citations · 106 across the 18 of their papers we have counts for
Showing 2011Show all
2 papers · 1 filter
cs.DS2011★ 1 cited
Improving Christofides' Algorithm for the s-t Path TSP
Hyung-Chan An, Robert Kleinberg, David B. Shmoys
We present a deterministic (1+sqrt(5))/2-approximation algorithm for the s-t path TSP for an arbitrary metric. Given a symmetric metric cost on n vertices including two prespecifie…
cs.DS2011★ 4 cited
LP-Based Approximation Algorithms for Traveling Salesman Path Problems
Hyung-Chan An, David B. Shmoys
This paper has been merged into 1110.4604.