Distributed algorithms for covering, packing and maximum weighted matching

摘要

This paper gives poly-logarithmic-round, dis tributed δ-approximation algorithms for covering problems with submodular cost and monotone covering constraints (SUBMODULAR-COST Covering). The approximation ratio S is the maximum number of variables in any constraint. Special cases include Covering Mixed Integer Linear Programs (CMIP), and Weighted Vertex Cover (with S = 2). Via duality, the paper also gives poly-logarithmic-round, distributed δ-approximation algorithms for Frac tional Packing linear programs (where S is the maximum number of constraints in which any variable occurs), and for Max Weighted c-Matching in hypergraphs (where S is the maximum size of any of the hyperedges; for graphs S = 2). The paper also gives parallel (RNC) 2-approxi-mation 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.1