期刊
DISTRIBUTED COMPUTING
卷 24, 期 1, 页码 45-63出版社
SPRINGER
DOI: 10.1007/s00446-011-0127-7
关键词
Approximation algorithms; Integer linear programming; Packing and covering; Vertex cover; Matching
This paper gives poly-logarithmic-round, distributed delta-approximation algorithms for covering problems with submodular cost and monotone covering constraints (Submodular-cost Covering). The approximation ratio delta is the maximum number of variables in any constraint. Special cases include Covering Mixed Integer Linear Programs (CMIP), and Weighted Vertex Cover (with delta = 2). Via duality, the paper also gives poly-logarithmic-round, distributed delta-approximation algorithms for Fractional Packing linear programs (where delta is the maximum number of constraints in which any variable occurs), and for Max Weighted c-Matching in hypergraphs (where delta is the maximum size of any of the hyperedges; for graphs delta = 2). The paper also gives parallel (RNC) 2-approximation algorithms for CMIP with two variables per constraint and Weighted Vertex Cover. The algorithms are randomized. All of the approximation ratios exactly match those of comparable centralized algorithms.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据