Research map / Learning theory and algorithms / Submodular and game algorithms
Breaking Barriers: Combinatorial Algorithms for Non-Monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives the first combinatorial parallel algorithm achieving a 1/e-ε approximation for size-constrained non-monotone submodular maximization with O(log n log k) adaptivity and O(n log n log k) queries, plus a simpler 1/4-ε high-probability variant.
Problem
Parallel (low-adaptivity) maximization of non-monotone submodular functions under a size constraint, where the best sublinear-adaptivity ratio was 1/e only via a continuous algorithm with costly oracle estimation.
Approach
A blended marginal gains analysis of interlaced greedy removes the branching guess over the top element's membership in the optimum, so a single solution family suffices; this is then parallelized via threshold sampling (Prefix-Selection, Distribute) into ParallelInterlaceGreedy and repeated into ParallelInterpolatedGreedy.
Key results
- PIG and PItG achieve the highest objective values on the er maxcut dataset, followed by ATG, FastRandomGreedy and ParSSP.
- PIG achieves second-best query efficiency across both main datasets, behind only the ATG/AdaptiveNonmonotoneMax-style nearly-linear methods in adaptivity.
- AdaptiveNonmonotoneMax and AST achieve the lowest adaptivity (O(log n)), while PIG and PItG achieve O(log n log k) adaptivity as theoretically predicted.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ParallelInterlaceGreedy instead of the evaluated baselines | Maximum Cut on er · er | normalized objective value | Helped |
| Use ParallelInterpolatedGreedy instead of AdaptiveNonmonotoneMax | Maximum Cut · er | normalized objective value | Helped |
| Use ParallelInterlaceGreedy or ParallelInterpolatedGreedy | Revenue Maximization · twitch-gamers | normalized objective value | Helped |
| Use ParallelInterlaceGreedy instead of other evaluated algorithms | Maximum Cut and Revenue Maximization · er and twitch-gamers | query efficiency | Mixed |
Surprising findings
- ParSSP has the highest query count among compared methods yet its binary search makes adaptive rounds worse than FastRandomGreedy on twitch-gamers.
Limitations
- Constants in the approximation and complexity are large (e.g., epsilon^-5 and epsilon^-6 factors), making the bounds loose in practice.
- PItG repeats PIG and its 1/e guarantee is only in expectation with probability 1-O(1/(eps n)).
Experimental setup
Datasets: er random graph (n=99,997) web-Google (n=875,713) musae-github (n=37,700) twitch-gamers (n=168,114)
Benchmarks: maxcut on er revmax on twitch-gamers maxcut and revmax on web-Google and musae-github (appendix)
Metrics: objective value normalized by ATG number of queries adaptive rounds
Baselines: FastRandomGreedy AdaptiveNonmonotoneMax AST ATG ParSSP
Builds on: InterlaceGreedy InterpolatedGreedy ThreshSeq RandomGreedy FastRandomGreedy
Closest papers by meaning
- Nearly Linear-Time, Parallelizable Algorithms for Non-Monotone Submodular Maximization (AAAI 2021 · similarity 0.95)
- Discretely beyond $1/e$: Guided Combinatorial Algortihms for Submodular Maximization (NeurIPS 2024 · similarity 0.94)
- Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel (NeurIPS 2021 · similarity 0.94)
- Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity (ICML 2021 · similarity 0.93)
- Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity (ICML 2019 · similarity 0.93)
- An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale (ICML 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.