期刊
JOURNAL OF COMBINATORIAL OPTIMIZATION
卷 8, 期 3, 页码 307-328出版社
SPRINGER
DOI: 10.1023/B:JOCO.0000038913.96607.c2
关键词
approximation algorithm; performance guarantee; linear relaxation; rounding technique; maximum coverage; max cut
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据