Distributed algorithms for covering, packing and maximum weighted matching

作者：Koufogiannakis Christos^*; Young Neal E

来源：Distributed Computing, 2011, 24(1): 45-63.

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.

• 出版日期2011-9