2 citations · 2 across the 4 of their papers we have counts for
4 papers
On Some Recent MAX SAT Approximation Algorithms
Matthias Poloczek, David P. Williamson, Anke van Zuylen
Recently a number of randomized 3/4-approximation algorithms for MAX SAT have been proposed that all work in the same way: given a fixed ordering of the variables, the algorithm ma…
Split Scheduling with Uniform Setup Times
Frans Schalekamp, Rene Sitters, Suzanne van der Ster +3
We study a scheduling problem in which jobs may be split into parts, where the parts of a split job may be processed simultaneously on more than one machine. Each part of a job req…
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…