# Submodular Function Maximization in Parallel via the Multilinear Relaxation

arXiv: https://arxiv.org/abs/1807.08678 · HTML: https://mlsanity.com/paper/1807.08678/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jul 2018.

## Built on by (most cited first, 8 of 8)

- [Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity](https://mlsanity.com/paper/2102.08327/) (2021)
- [Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel](https://mlsanity.com/paper/2111.07917/) (2021)
- [Instance Specific Approximations for Submodular Maximization](https://mlsanity.com/paper/2102.11911/) (2021)
- [Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models](https://mlsanity.com/paper/2206.09563/) (2022)
- [Practical Parallel Algorithms for Non-Monotone Submodular Maximization](https://mlsanity.com/paper/2308.10656/) (2023)
- [E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time](https://mlsanity.com/paper/2506.07747/) (2025)
- [Sample-Adaptivity Tradeoff in On-Demand Sampling](https://mlsanity.com/paper/2511.15507/) (2025)
- [GreedyML: A Parallel Algorithm for Maximizing Constrained Submodular Functions](https://mlsanity.com/paper/2403.10332/) (2024)

## Abstract (arXiv)

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-ε)-approximation in O(log n/ε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 ∈ [0,1]n subject to Ax ≤ 1 where F is the multilinear relaxation of a monotone submodular function. Our algorithm achieves a near-optimal (1-1/e-ε)-approximation in O(log2 m log n/ε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.