Research map / Learning theory and algorithms / Submodular and game algorithms
Fast and Private Submodular and $k$-Submodular Functions Maximization with Matroid Constraints
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use continuous greedy with a discretized matroid polytope and exponential-mechanism selection | Monotone submodular maximization under matroid constraints · Matroid constraints | approximation ratio: \frac{1}{2} -> (1-\frac{1}{\mathrm{e}}) | Helped |
| Estimate layer sizes by sampling rather than evaluate every point in the covering (ablation) | Differentially Private Continuous Greedy · Monotone submodular maximization under matroid constraints | function evaluations: O(r(\mc{M})|E|^{1+({\frac{r(\mc{M})}{\epsilon}})^2}) -> O(r(\mc{M})|E|^2\ln{\frac{|E|}{\epsilon}}) | Helped |
| Use the exponential mechanism to select feasible element-label pairs | Monotone k-submodular maximization under matroid constraints · Matroid constraints | approximation ratio: No differentially private algorithm -> \frac{1}{2} approximation | Helped |
| Sample a subset of candidate elements at each iteration (ablation) | Differentially private k-submodular maximization · Monotone k-submodular maximization under matroid constraints | function evaluations: O(k|E|r(\mc{M})) -> O\left(k|E|\ln{r(\mc{M})} \ln{\frac{r(\mc{M})}{\gamma}} \right) | Helped |
Closest papers by meaning
- Differentially Private Submodular Maximization: Data Summarization in Disguise (ICML 2017 · similarity 0.93)
- Differentially Private Submodular Maximization with a Knapsack Constraint (ICML 2026 · similarity 0.93)
- Improved Algorithms for Fair Matroid Submodular Maximization (NeurIPS 2025 · similarity 0.90)
- Online Two-Stage Submodular Maximization (NeurIPS 2025 · similarity 0.89)
- Discretely beyond $1/e$: Guided Combinatorial Algortihms for Submodular Maximization (NeurIPS 2024 · similarity 0.88)
- A Unified Approach to Submodular Maximization Under Noise (NeurIPS 2025 · similarity 0.87)
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.