  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. Our algorithm achieves a near-optimal
$(1-1/e-\epsilon)$-approximation in $O(\log^2 m \log n/\epsilon^4)$ rounds
where $n$ is the cardinality of the ground set and $m$ is the number of packing
constraints. For many constraints of interest, the resulting fractional
solution can be rounded via known randomized rounding schemes that are
oblivious to the specific submodular function. We thus derive randomized
algorithms with poly-logarithmic adaptivity for a number of constraints
including partition and laminar matroids, matchings, knapsack constraints, and
their intersections.
