tlooto
Sign up
MathematicsComputer Science

Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance Guarantee

A. Ageev, M. Sviridenko

2004.9.1JOURNAL OF COMBINATORIAL OPTIMIZATION

DOI: 10.1023/b:joco.0000038913.96607.c2

tlooto Summary

The paper presents a general method of designing constant-factor approximation algorithms for some discrete optimization problems with assignment-type constraints with better performance guarantees for some well-known problems including MAXIMUM COVERAGE, MAX CUT and some of their generalizations.

Abstract

Abstract is not available.

Citation format

AGEEV, A.; SVIRIDENKO, M. Pipage rounding: A new method of constructing algorithms with proven performance guarantee. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2004, 8: 307–328.