Pipage rounding: A new method of constructing algorithms with proven performance guarantee

被引：231

作者：

Ageev, AA

Sviridenko, MI

机构：

[1] Sobolev Inst Math, Novosibirsk 630090, Russia

[2] IBM Corp, Thomas J Watson Res Ctr, Yorktown Hts, NY 10598 USA

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2004年 / 8卷 / 03期

基金：

俄罗斯基础研究基金会;

关键词：

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

D O I：

10.1023/B:JOCO.0000038913.96607.c2

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

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.

引用

页码：307 / 328

页数：22

共 22 条

[1]

Ageev AA, 1999, LECT NOTES COMPUT SC, V1610, P17

[2]

AGEEV AA, 2000, LECT NOTES COMPUTER, V1879, P32

[3] Better approximation algorithms for SET SPLITTING and NOT-ALL-EQUAL SAT [J].