Research map / Learning theory and algorithms / Submodular and game algorithms
Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint
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.
Proposes a practical non-monotone submodular maximization algorithm under a cardinality constraint with 0.385 approximation and O(n+k^2) queries, built from fast local search and guided stochastic greedy.
Problem
Non-monotone submodular maximization subject to a cardinality constraint, where the best known approximations are impractically slow and the practical algorithms only achieve 1/e.
Approach
Combines an accelerated local search (sampling-based swaps, O(n+k^2) queries) with a guided stochastic greedy that reuses Sample Greedy ideas, achieving a 0.385 guarantee with near-linear query complexity and returning the better of the two solutions.
Key results
- Achieves a 0.385-approximation with O(n+k^2) query complexity for non-monotone submodular maximization under a cardinality constraint, improving on the 1/e of practical state-of-the-art.
- In experiments on movie recommendation, image summarization, and revenue maximization, the proposed algorithm outperforms Random Greedy and Sample Greedy in objective value.
- Reported standard deviations across runs are lower than those of competitors, indicating more stable outputs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed algorithm instead of the practical comparison algorithms | Movie recommendation on MovieLens · MovieLens movie recommendation | objective function value | Helped |
| Use the proposed algorithm instead of the comparison algorithms | Personalized image summarization · CIFAR10 image summarization | objective function value | Helped |
| Use the proposed algorithm instead of the comparison algorithms | Personalized image summarization · CIFAR100 image summarization | objective function value | Helped |
| Use the proposed algorithm instead of Random Greedy and Sample Greedy | Revenue maximization · Facebook network | objective function value | Helped |
| Use the proposed algorithm instead of Random Greedy and Sample Greedy | Revenue maximization · Advogato network | objective function value | Helped |
| Use the proposed algorithm instead of the comparison algorithms | Personalized image summarization · CIFAR10 and CIFAR100 image summarization | standard deviation | Helped |
| Use the proposed algorithm instead of Random Greedy and Sample Greedy | Revenue maximization · Facebook and Advogato networks | standard deviation | Helped |
Limitations
- Practical version replaces the theoretical sample-size parameter p with 8/(k·epsilon), so the theoretical guarantee does not directly apply to experiments.
- Guarantee is for cardinality constraints only; the paper notes derandomization and other constraints are handled by independent work.
- Hardware is a CPU laptop (i9-13980HX), not GPU-based; experiments are on a single machine.
Experimental setup
Datasets: MovieLens CIFAR10 CIFAR100 Facebook network Advogato network
Benchmarks: MovieLens CIFAR10 CIFAR100 Facebook network Advogato network
Metrics: objective function value standard deviation across 8 runs
Baselines: Random Greedy Sample Greedy Random Sampling
Builds on: Random Greedy Sample Greedy Buchbinder and Feldman 0.385-approximation Lovász extension
Closest papers by meaning
- Submodular Maximization in Clean Linear Time (NeurIPS 2022 · similarity 0.93)
- Consistent Submodular Maximization (ICML 2024 · similarity 0.91)
- Online and Streaming Algorithms for Constrained k-Submodular Maximization (AAAI 2025 · similarity 0.90)
- Deletion-Robust Submodular Maximization with Knapsack Constraints (AAAI 2024 · similarity 0.90)
- An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale (ICML 2025 · similarity 0.90)
- Non-monotone Sequential Submodular Maximization (AAAI 2024 · 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.