Pipage rounding: a new method of constructing algorithms with proven performance guarantee. (English) Zbl 1084.90029

Ageev, A. A.; Sviridenko, M. I.

J. Comb. Optim. 8, No. 3, 307-328 (2004).

Summary: The paper presents a general method of designing constant-factor approximation algorithms for some discrete optimization problems with assignment-type constraints. The core of the method is a simple deterministic procedure of rounding of linear relaxations (referred to as pipage rounding). With the help of the method we design approximation algorithms with better performance guarantees for some well-known problems including MAXIMUM COVERAGE, MAX CUT with given sizes of parts and some of their generalizations.

MSC:

90C09	Boolean programming
90C27	Combinatorial optimization
68W25	Approximation algorithms

Keywords:

Approximation algorithm; performance guarantee; linear relaxation; rounding technique; maximum coverage; max cut