7 citations · 18 across the 10 of their papers we have counts for
6 papers · 1 filter
A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest
Neil Olver, Frans Schalekamp, Suzanne van der Ster +2
We give a 2-approximation algorithm for the Maximum Agreement Forest problem on two rooted binary trees. This NP-hard problem has been studied extensively in the past two decades,…
A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest
Frans Schalekamp, Anke van Zuylen, Suzanne van der Ster
We give a 2-approximation algorithm for the Maximum Agreement Forest problem on two rooted binary trees. This NP-hard problem has been studied extensively in the past two decades,…
Scheduling over Scenarios on Two Machines
Esteban Feuerstein, Alberto Marchetti-Spaccamela, Frans Schalekamp +4
We consider scheduling problems over scenarios where the goal is to find a single assignment of the jobs to the machines which performs well over all possible scenarios. Each scena…
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…