Graph algorithms, Hypergraphs; F.2.2 [ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY]: Nonnumerical Algorithms and Problems—Computations on

The paper presents distributed and parallel δ-approximation algorithms for covering problems, where δ is the maximum number of variables on which any constraint depends (for example, δ = 2 for vertex cover). Specific results include the following. • For weighted vertex cover, the first distributed 2-ap-proximation algorithm taking O(logn) rounds and the first parallel 2-approximation algorithm in RNC. The algorithms generalize to covering mixed integer linear programs (CMIP) with two variables per constraint (δ = 2). • For any covering problem with monotone constraints and submodular cost, a distributed δ-approximation algo-rithm taking O(log2 |C|) rounds, where |C | is the number of constraints. (Special cases include CMIP, facility location, and probabilistic (two-stage) variants of these problems.