Williamson David P.

David P. Williamson

Information about the author David P. Williamson will soon be added to the site.
Found 10 papers in total
A simpler and better derandomization of an approximation algorithm for single source rent-or-buy
A simpler and better derandomization of an approximation algorithm for single source rent-or-buy
2007
We present a very simple way of derandomizing the algorithm proposed by Gupta, Kumar...
A 1.47-approximation algorithm for a preemptive single-machine scheduling problem
A 1.47-approximation algorithm for a preemptive single-machine scheduling problem
2000
In this note, we give a 1.47-approximation algorithm for the preemtpive scheduling of...
Gadgets, approximation, and linear programming
Gadgets, approximation, and linear programming
2000
We present a linear programming-based method for finding ‘gadgets,’ i.e.,...
Short shop schedules
Short shop schedules
1997
We consider the open shop, job shop, and flow shop scheduling problems with integral...
An efficient approximation algorithm for the survivable network design problem
An efficient approximation algorithm for the survivable network design problem
1998
The survivable network design problem is to construct a minimum-cost subgraph...
Computational experience with an approximation algorithm on large-scale Euclidean matching instances
Computational experience with an approximation algorithm on large-scale Euclidean matching instances
1996
We consider a 2-approximation algorithm for Euclidean minimum-cost perfect matching...
Computational experience with an approximation algorithm on large-scale Euclidean matching instances
Computational experience with an approximation algorithm on large-scale Euclidean matching instances
1996
The authors consider a 2-approximation algorithm for Euclidean minimum-cost perfect...
Approximating minimum-cost graph problems with spanning tree edges
Approximating minimum-cost graph problems with spanning tree edges
1994
Building on work of Imielinska, Kalantari and Khachiyan, the authors show how to find...
Analysis of the Held-Karp lower bound for the asymmetric TSP
Analysis of the Held-Karp lower bound for the asymmetric TSP
1992
The paper shows that the Held-Karp lower bound for the asymmetric traveling salesman...
Permutation vs. non-permutation flow shop schedules
Permutation vs. non-permutation flow shop schedules
1991
In studying the m -machine flow shop scheduling problem, it is common practice to...
Papers per page: