Back to Search
Start Over
The primal-dual method for approximation algorithms.
- Source :
- Mathematical Programming; 2002, Vol. 91 Issue 3, p447, 32p
- Publication Year :
- 2002
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00255610
- Volume :
- 91
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- Mathematical Programming
- Publication Type :
- Academic Journal
- Accession number :
- 6296381
- Full Text :
- https://doi.org/10.1007/s101070100262