31 citations · 69 across the 12 of their papers we have counts for
Showing 2009 · cs.DSShow all
2 papers · 2 filters
cs.DS2009★ 21 cited
Combining Approximation Algorithms for the Prize-Collecting TSP
Michel X. Goemans
We present a 1.91457-approximation algorithm for the prize-collecting travelling salesman problem. This is obtained by combining a randomized variant of a rounding algorithm of Bie…
cs.DS2009★ 7 cited
A Randomized Rounding Algorithm for the Asymmetric Traveling Salesman Problem
Michel X. Goemans, Nicholas J. A. Harvey, Kamal Jain +1
We present an algorithm for the asymmetric traveling salesman problem on instances which satisfy the triangle inequality. Like several existing algorithms, it achieves approximatio…