Primal-dual approximation algorithms.

• F.A. Chudak, M.X. Goemans, D.S. Hochbaum and D.P. Williamson, A primal--dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs, Operations Research Letters, 22, 111--118, 1998. Reprint.

• M.X. Goemans and D.P. Williamson, Primal-Dual Approximation Algorithms for Feedback Problems in Planar Graphs, Combinatorica, 17, 1--23, 1997. pdf.

• Survey. M.X. Goemans and D.P. Williamson, The Primal-Dual Method for Approximation Algorithms and its Application to Network Design Problems, in Approximation Algorithms, D. Hochbaum, Ed., 1997. pdf

• D.P. Williamson and M.X. Goemans, Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances, ORSA J. Computing, 8, 29--40, 1996. A preliminary version appeared in the Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, VA, 355--364, 1994. pdf.

• M.X. Goemans, A. Goldberg, S. Plotkin, D. Shmoys, E. Tardos and D. Williamson, Improved Approximation Algorithms for Network Design Problems, Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, VA, 223--232, 1994.

• H.N. Gabow, M.X. Goemans and D.P. Williamson, An Efficient Approximation Algorithm for the Survivable Network Design Problem, Mathematical Programming, 82, 13--40, 1998.

• D. Williamson, M.X. Goemans, M. Mihail and V. Vazirani, A Primal-Dual Approximation Algorithm for Generalized Steiner Network Problems, Combinatorica, 15, 435--454, 1995.

• M.X. Goemans and D.P. Williamson, Approximating minimum-cost graph problems with spanning tree edges, Operations Research Letters, 16, 183--244, 1994.

• M.X. Goemans and D.P. Williamson, A General Approximation Technique for Constrained Forest Problems, SIAM Journal on Computing, 24, 296--317, 1995. pdf.