Submodular Function Maximization in Parallel via the Multilinear Relaxation

Understand

Balkanski and Singer [5] recently initiated the study of adaptivity (or parallelism) for constrained submodular function maximization, and studied the setting of a cardinality constraint.

• Very recent improvements for this problem by Balkanski, Rubinstein, and Singer [6] and Ene and Nguyen [21] resulted in a near-optimal $(1-1/e-\epsilon)$-approximation in $O(\log n/\epsilon^2)$ rounds of adaptivity.
• Partly motivated by the goal of extending these results to more general constraints, we describe parallel algorithms for approximately maximizing the multilinear relaxation of a monotone submodular function subject to packing constraints.
• Formally our problem is to maximize $F(x)$ over $x \in [0,1]^{n}$ subject to $Ax \le 1$ where $F$ is the multilinear relaxation of a monotone submodular function.