zbMATH — the first resource for mathematics

Pipage rounding: a new method of constructing algorithms with proven performance guarantee. (English) Zbl 1084.90029
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.

90C09 Boolean programming
90C27 Combinatorial optimization
68W25 Approximation algorithms
Full Text: DOI