Research map / Learning theory and algorithms / Submodular and game algorithms
Deletion-Robust Submodular Maximization with Knapsack Constraints
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 RSK-Streaming, a single-pass deletion-robust streaming algorithm for submodular maximization under d knapsack constraints that handles non-monotone objectives and improves the monotone approximation ratio.
Problem
Deletion-robust submodular maximization under knapsack constraints (RSK): selecting a feasible subset after an adversary removes up to r elements, in a streaming setting, where prior work only handled the monotone case with a poor ratio.
Approach
A two-stage streaming summary-and-mining algorithm that guesses a density threshold via the (r+1)-th highest-density element, maintains h candidate solutions with warehouses, and randomly samples elements with probability inversely proportional to marginal gain so that deletions cause bounded loss.
Key results
- For non-monotone RSK, RSK-Streaming achieves approximation ratio 1/(6.82+2.63d) with summary size Õ(k+r).
- For monotone RSK, the algorithm achieves 1/(2+2d) approximation, improving on the prior (1-1/e)^(3/d+8)/(128(1+2d)) ratio of AlgMult.
- In influence maximization, RSKS achieves utility gains of up to 350% (299% on average) over AlgMult and stores over two orders of magnitude fewer elements.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RSK-Streaming instead of AlgMult | Robust influence maximization · epinions and wiki | utility: performance gains of up to 350% (and 299% on average) | Helped |
| Use RSK-Streaming instead of AlgMult | Robust influence maximization · epinions and wiki | summary size: more than two orders of magnitude | Helped |
| Increase the number of removed elements | RSK-Streaming · Robust influence maximization | utility: up to a maximum of 6% | Hurt |
| Use RSK-Streaming instead of the omniscient SMMK baseline | Robust influence maximization · epinions and wiki | utility | No clear effect |
Surprising findings
- Utility of RSKS drops by at most 6% as the number of removed elements increases, while the omniscient KnapsackStreaming baseline is matched closely.
Limitations
- Experiments only on influence maximization (and movie recommendation in appendix) with the removal set generated by an offline algorithm.
- Approximation guarantees rely on oblivious adversary assumption (no access to random bits).
- Non-monotone ratio of 1/(6.82+2.63d) is far from the best known offline ratios.
Experimental setup
Datasets: epinions wiki
Benchmarks: epinions influence maximization wiki influence maximization
Metrics: objective value (utility) summary size approximation ratio
Baselines: AlgMult KnapsackStreaming SMMK
Builds on: Mitrovic et al. 2017 partitioned thresholding Avdiukhin et al. 2019 AlgMult Kazemi et al. 2018 deletion-robust sampling Buchbinder and Feldman 2019 offline 0.385 algorithm Han et al. 2021 SMMK
Closest papers by meaning
- Online and Streaming Algorithms for Constrained k-Submodular Maximization (AAAI 2025 · similarity 0.94)
- Submodular Maximization in Clean Linear Time (NeurIPS 2022 · similarity 0.92)
- Streaming Submodular Maximization under a k-Set System Constraint (ICML 2020 · similarity 0.92)
- Robust Submodular Maximization: A Non-Uniform Partitioning Approach (ICML 2017 · similarity 0.91)
- Deletion-Robust Submodular Maximization: Data Summarization with “the Right to be Forgotten” (ICML 2017 · similarity 0.91)
- Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint (NeurIPS 2024 · 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.