9 citations · 26 across the 13 of their papers we have counts for
Showing 2011Show all
3 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.DM2011
A Diameter-Revealing Proof of the Bondy-Lovász Lemma
Hyung-Chan An, Robert Kleinberg
We present a strengthened version of a lemma due to Bondy and Lovász. This lemma establishes the connectivity of a certain graph whose nodes correspond to the spanning trees of a 2…
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.