David P. Williamson
Home
Posts
Publications
Talks
Courses
Contact
CV
Michel X. Goemans
Latest
Approximating the smallest $k$-edge connected spanning subgraph by LP-rounding.
Approximation Algorithms for MAX 3-CUT and Other Problems via Complex Semidefinite Programming.
Two-dimensional Gantt charts and a scheduling algorithm of Lawler.
A 1.47-approximation algorithm for a preemptive single-machine scheduling problem.
An Efficient Approximation Algorithm for the Survivable Network Design Problem.
A Primal-Dual Interpretation of Two 2-Approximation Algorithms for the Feedback Vertex Set Problem in Undirected Graphs.
Primal-dual approximation algorithms for feedback problems in planar graphs.
The primal-dual method for approximation algorithms and its application to network design problems.
Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances.
A Primal-Dual Approximation Algorithm for Generalized Steiner Network Problems.
A general approximation technique for constrained forest problems.
Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming
Approximating minimum-cost graph problems with spanning tree edges.
New 3/4-Approximation Algorithms for the Maximum Satisfiability Problem.
A note on the prize-collecting traveling salesman problem.
Cite
×