Research map / Learning theory and algorithms / Submodular and game algorithms
Consistent 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.
Studies streaming monotone submodular maximization under cardinality constraints with consistency (bounded solution changes per insertion), giving a 1-consistent 3.147-approximation (Encompassing-Set), an Õ(1/ε)-consistent 2.619-approximation (Chasing-Local-Opt), and a lower bound of 2 for constant-consistent deterministic algorithms.
Problem
Maintaining a constant-factor approximate solution to monotone submodular maximization under a cardinality constraint in a streaming/insertion-only setting while keeping consecutive solutions stable (few changes per step).
Approach
Replace the swap-oldest or swap-min rules with a benchmark-set rule (Encompassing-Set: add to a benchmark set if marginal gain exceeds (β/k)f(B), keep last k as solution) and a local-optimum chasing rule (Chasing-Local-Opt: golden-ratio insertion threshold, min-value swap, plus up to N extra swaps per step toward a local optimum) to improve the approximation-consistency trade-off over Swapping.
Key results
- Encompassing-Set is 1-consistent with a 3.147+O(1/k) approximation, improving on Swapping's 4.
- Chasing-Local-Opt achieves a (φ+1+9ε) ≈ 2.619+O(ε) approximation with Õ(1/ε) consistency.
- Lower bound: no deterministic C-consistent algorithm achieves a (2-ε)-approximation; experiments show Swapping makes about 25x more changes than the proposed algorithms in one setting while Sieve-Streaming changes 3-4x more often.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Encompassing-Set instead of Swapping | Monotone submodular maximization under cardinality constraint · Monotone submodular maximization under cardinality constraint | approximation factor: 4 -> 3.147 + O(\nicefrac{1}{k}) | Helped |
| Use Chasing-Local-Opt instead of Swapping | Monotone submodular maximization under cardinality constraint · Monotone submodular maximization under cardinality constraint | approximation factor: 4 -> (\phi + 1 + 9\varepsilon) | Helped |
| Use Chasing-Local-Opt instead of Encompassing-Set | Monotone submodular maximization under cardinality constraint · Monotone submodular maximization under cardinality constraint | approximation factor: 3.147 + O(\nicefrac{1}{k}) -> (\phi + 1 + 9\varepsilon) | Helped |
| Use Encompassing-Set or Chasing-Local-Opt instead of Sieve-Streaming | Real-world submodular maximization experiments · Facebook influence maximization; RunInRome k-medoid and LogDet | objective value | No clear effect |
| Use Encompassing-Set or Chasing-Local-Opt instead of Swapping | Real-world submodular maximization experiments · Facebook influence maximization; RunInRome k-medoid and LogDet | cumulative number of changes: around a factor 25 | Helped |
| Use Encompassing-Set or Chasing-Local-Opt instead of Sieve-Streaming | Real-world submodular maximization experiments · Facebook influence maximization | cumulative number of changes: 3-4 times | Helped |
| Use Encompassing-Set or Chasing-Local-Opt instead of Sieve-Streaming | Real-world submodular maximization experiments · Additional experimental settings | cumulative number of changes: about 500x and 10x | Helped |
| Use Encompassing-Set or Chasing-Local-Opt instead of Swapping | Real-world submodular maximization experiments · Additional experimental settings | cumulative number of changes: between 50\% and 100\% more | Helped |
| Use Encompassing-Set or Chasing-Local-Opt on the synthetic hard instance | Worst-case weighted covering instance · Weighted covering | approximation guarantee improvement: 21.325\% and 34.525\% | Helped |
| Require arriving elements to pass the marginal-value threshold and retain the last k accepted elements | Encompassing-Set · Monotone submodular maximization under cardinality constraint | approximation factor: 3.147 + O(\nicefrac 1k) | Helped |
| Perform up to N additional swaps toward a local optimum | Chasing-Local-Opt · Monotone submodular maximization under cardinality constraint | approximation factor: (\phi + 1 + 9\varepsilon) | Helped |
Surprising findings
- Swapping, despite being 1-consistent, is significantly less consistent in aggregate than proposed algorithms in some settings, while Sieve-Streaming changes solutions orders of magnitude more often (about 500x in one setting).
Limitations
- null
Experimental setup
Datasets: Facebook social network graph RunInRome geolocation dataset Uber pickups dataset MovieLens 1M synthetic weighted covering instance
Benchmarks: Facebook influence maximization RunInRome k-medoid RunInRome LogDet Uber k-medoid Uber LogDet MovieLens personalized recommendation weighted covering synthetic instance
Metrics: objective value cumulative number of solution changes (consistency) approximation ratio
Baselines: Swapping Sieve-Streaming Sieve-Streaming++ greedy recomputation
Builds on: Swapping (Chakrabarti and Kale 2014) Sieve-Streaming greedy algorithm
Closest papers by meaning
- A General Framework for Dynamic Consistent Submodular Maximization (ICML 2026 · similarity 0.94)
- Fully Dynamic Algorithm for Constrained Submodular Optimization (NeurIPS 2020 · similarity 0.93)
- Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity (ICML 2019 · similarity 0.92)
- Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization (NeurIPS 2018 · similarity 0.92)
- Nearly Linear-Time, Parallelizable Algorithms for Non-Monotone Submodular Maximization (AAAI 2021 · similarity 0.92)
- Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint (NeurIPS 2024 · similarity 0.91)
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.