Showing cs.DSShow all
2 papers · 1 filter
cs.DS2011
A note on the generalized min-sum set cover problem
Martin Skutella, David P. Williamson
In this paper, we consider the generalized min-sum set cover problem, introduced by Azar, Gamzu, and Yin. Bansal, Gupta, and Krishnaswamy give a 485-approximation algorithm for the…
cs.DS2011
A Proof of the Boyd-Carr Conjecture
Frans Schalekamp, David P. Williamson, Anke van Zuylen
Determining the precise integrality gap for the subtour LP relaxation of the traveling salesman problem is a significant open question, with little progress made in thirty years in…