Lisa Fleischer, Kamal Jain, et al.
Annual Symposium on Foundations of Computer Science - Proceedings
In this survey, we give an overview of a technique used to design and analyze algorithms that provide approximate solutions to NP-hard problems in combinatorial optimization. Because of parallels with the primal-dual method commonly used in combinatorial optimization, we call it the primal-dual method for approximation algorithms. We show how this technique can be used to derive approximation algorithms for a number of different problems, including network design problems, feedback vertex set problems, and facility location problems.
Lisa Fleischer, Kamal Jain, et al.
Annual Symposium on Foundations of Computer Science - Proceedings
Andreas S. Schulz, David B. Shmoys, et al.
PNAS
Allan Borodin, Jon Kleinberg, et al.
Journal of the ACM
David P. Williamson, Michel X. Goemans, et al.
Combinatorica