Journal
JOURNAL OF COMBINATORIAL OPTIMIZATION
Volume 8, Issue 3, Pages 307-328Publisher
SPRINGER
DOI: 10.1023/B:JOCO.0000038913.96607.c2
Keywords
approximation algorithm; performance guarantee; linear relaxation; rounding technique; maximum coverage; max cut
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available