Research map / Learning theory and algorithms / Submodular and game algorithms
A Dynamic Algorithm for Weighted Submodular Cover Problem
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 fully dynamic algorithm for weighted submodular cover under element insertions/deletions, achieving an expected (1-O(ε), O(1/ε))-bicriteria approximation with polylogarithmic amortized oracle queries per update.
Problem
Maintaining an approximately minimum-cost cover (submodular cover with element weights) when ground-set elements are inserted and deleted dynamically, with low per-update query complexity.
Approach
Extends the multi-level dynamic submodular maximization framework to arbitrary weights by bucketing elements two-dimensionally (by marginal density and weight), sampling the largest bucket with a simulation-chosen sample size, and partially reconstructing levels only when deletions/insertions affect them; parallel runs over geometric thresholds handle the cost-value trade-off.
Key results
- Algorithm maintains an expected (1-O(ε), O(ε^{-1}))-bicriteria approximation for dynamic weighted submodular cover.
- Expected amortized query complexity poly(log n, log ρ, 1/ε) per update, where ρ is the weight ratio.
- Theoretical result only; no experiments reported in the provided text.
Limitations
- Query complexity depends on n through the bound polylog(n) and on weight ratio ρ, not fully independent of n.
- Guarantees are bicriteria and hold in expectation only, with the cost bound O(1/ε) times optimal.
- Monotone submodular functions only; non-monotone dynamic cover is left open.
Experimental setup
Metrics: expected approximation ratio bicriteria cost ratio amortized query complexity
Builds on: dynamic submodular maximization multi-level construction streaming submodular cover bicriteria algorithm
Closest papers by meaning
- Bicriteria Approximation Algorithms for the Submodular Cover Problem (NeurIPS 2023 · similarity 0.91)
- Dynamic Constrained Submodular Optimization with Polylogarithmic Update Time (ICML 2023 · similarity 0.89)
- A Near Linear Query Lower Bound for Submodular Maximization (ICML 2025 · similarity 0.89)
- Fair Submodular Cover (ICLR 2025 · similarity 0.87)
- Breaking Barriers: Combinatorial Algorithms for Non-Monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation (ICML 2025 · similarity 0.85)
- Discretely beyond $1/e$: Guided Combinatorial Algortihms for Submodular Maximization (NeurIPS 2024 · similarity 0.85)
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.