7 citations · 12 across the 22 of their papers we have counts for
3 papers · 2 filters
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…
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…
On the Integrality Gap of the Subtour LP for the 1,2-TSP
Jiawei Qian, Frans Schalekamp, David P. Williamson +1
In this paper, we study the integrality gap of the subtour LP relaxation for the traveling salesman problem in the special case when all edge costs are either 1 or 2. For the gener…