Submodular Maximization with Packing Constraints in Parallel
share
We consider the problem of maximizing the multilinear extension of a submodular function subject to packing constraints in parallel. For monotone functions, we obtain a 1-1/e-ϵ approximation using O((n/ϵ)(m)/ϵ^2) rounds of adaptivity and evaluations of the function and its gradient, where m is the number of packing constraints and n is the number of variables. For non-monotone functions, we obtain a 1/e-ϵ approximation using O((n/ϵ)(1/ϵ)(n+m)/ϵ^2) rounds of adaptivity and evaluations of the function and its gradient. Our results apply more generally to the problem of maximizing a diminishing returns submodular (DR-submodular) function subject to packing constraints.
READ FULL TEXT
