The primal-dual method for approximation algorithms
DP Williamson - Mathematical Programming, 2002 - Springer
Mathematical Programming, 2002•Springer
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 …
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 …
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.
Springer