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.