Research map / Learning theory and algorithms / Submodular and game algorithms
Discretely beyond $1/e$: Guided Combinatorial Algortihms for Submodular Maximization
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.
Breaks the 1/e barrier for combinatorial non-monotone submodular maximization by guiding RandomGreedy with a fast local search output, reaching 0.385 (size) and 0.305 (matroid), with deterministic and nearly linear-time variants.
Problem
Constrained non-monotone submodular maximization in the value oracle model: all known ratios above 1/e use continuous (multilinear extension) methods with very high query complexity, and the best combinatorial ratio is 1/e (size) and 0.283 (matroid).
Approach
Use a fast local search (FastLS) to produce a guidance set Z with low value and poor overlap with the optimum, then run RandomGreedy on the ground set excluding Z for an initial phase before switching to the full ground set; the analysis via new recurrences yields ratios above 1/e combinatorially. Deterministic variants guide InterpolatedGreedy instead.
Key results
- Randomized combinatorial algorithm achieves ratio 0.385 - eps for size constraint in O(kn/eps) queries, and 0.305 - eps for matroid constraint, versus 1/e and 0.283 for RandomGreedy.
- Deterministic version keeps the same ratios with query complexity O(kn * l^(2l-1)), l = 10/(9 eps).
- Deterministic nearly linear-time algorithm achieves 0.377 - eps in O(n log k) queries (for fixed eps).
- Empirically, FastLS+GuidedRG outperforms StandardGreedy and RandomGreedy in objective value, using about twice the queries of StandardGreedy and 10x-100x fewer than the prior local search.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Guide RandomGreedy with FastLS | RandomGreedy · Size constraint | approximation ratio: 1/e approx 0.367 -> 0.385- epsi | Helped |
| Guide RandomGreedy with FastLS | RandomGreedy · Matroid constraint | approximation ratio: 0.283 -> 0.305- epsi | Helped |
| Use deterministic GuidedIG in place of Guided RandomGreedy | Guided RandomGreedy · Size constraint | approximation ratio: 0.385- epsi | No clear effect |
| Use deterministic GuidedIG in place of Guided RandomGreedy | Guided RandomGreedy · Matroid constraint | approximation ratio: 0.305- epsi | No clear effect |
| Use intermediate solutions of unguided InterpolatedGreedy to find the guidance set | Deterministic guided InterpolatedGreedy · Size constraint | approximation ratio: 0.385- epsi -> 0.377- epsi | Mixed |
| Use FastLS + GuidedRG | Size-constrained submodular maximization · Video summarization | objective value | Helped |
| Use FastLS + GuidedRG | Size-constrained submodular maximization · Maximum cut | objective value | Helped |
| Use FastLS + GuidedRG instead of StandardGreedy | Size-constrained submodular maximization · Video summarization and maximum cut | query count | Hurt |
| Use FastLS + GuidedRG instead of the prior local search algorithm | Size-constrained submodular maximization · Video summarization and maximum cut | query count: factor of 10; factor of 100 | Helped |
Surprising findings
- The continuous 0.385 algorithm of prior work has query complexity O(n^11 log n) on the set function, making it impractical even for small instances.
Limitations
- Query complexity is quadratic in n when k is on the order of n.
- Deterministic algorithms have exponential dependence on 1/eps, making them impractical.
- Empirical evaluation limited to video summarization and maximum cut on synthetic graphs with size constraint.
Experimental setup
Datasets: Erdős-Rényi graphs Barabási-Albert graphs Watts-Strogatz graphs video summarization frames (n=100)
Benchmarks: video summarization (DPP objective, n=100) maximum cut on graphs (n=10000)
Metrics: objective value number of queries
Baselines: StandardGreedy RandomGreedy Local search of Lee et al. (1/4 - eps, matroid) Continuous 0.385 algorithm of Buchbinder and Feldman
Builds on: RandomGreedy InterpolatedGreedy measured continuous greedy stochastic greedy
Closest papers by meaning
- Breaking Barriers: Combinatorial Algorithms for Non-Monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation (ICML 2025 · similarity 0.94)
- Deterministic Approximation for Submodular Maximization over a Matroid in Nearly Linear Time (NeurIPS 2020 · similarity 0.92)
- Nearly Linear-Time, Parallelizable Algorithms for Non-Monotone Submodular Maximization (AAAI 2021 · similarity 0.92)
- Improved Fully Dynamic Submodular Maximization Under Matroid Constraints (AAAI 2026 · similarity 0.91)
- An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale (ICML 2025 · similarity 0.90)
- A Unified Approach to Submodular Maximization Under Noise (NeurIPS 2025 · similarity 0.89)
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.