Research map / Learning theory and algorithms / Submodular and game algorithms
An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
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 scalable discrete LP-greedy algorithm for multiobjective (max-min) submodular maximization that nearly achieves the 1-1/e approximation without multilinear extension, and applies it to fair centrality and fair influence maximization.
Problem
Maximizing the minimum of k monotone submodular functions under a cardinality constraint; prior algorithms either have weak guarantees or rely on costly multilinear extension evaluations, which do not scale.
Approach
Greedy where each step samples an element from a distribution solving an LP that guarantees expected marginal gain for every color relative to the gap to OPT; a martingale/adaptive-adversary concentration bound makes the output good for all colors simultaneously, with MWU and lazy evaluations for efficiency.
Key results
- On max-k-cover with k=20 colors, LP Greedy achieves the highest objective with fewer function evaluations than Udwani MWU, the only other algorithm with theoretical guarantees.
- On fair centrality maximization (Arts, Crafts & Sewing, n=5051, k=2), the method achieves the highest objective with fewer evaluations than Udwani MWU and Saturate.
- Theoretical running time O(nB^3 eps^-2 k log k log(1/delta)) and O(nBk log(1/delta)) function evaluations, versus Õ(kn^8) for the prior (1-1/e-eps) algorithm of Udwani-style continuous methods, and the Frank-Wolfe method requiring multilinear extension evaluations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the proposed LP Greedy algorithm instead of prior algorithms | multiobjective submodular maximization · max-k-cover, Kronecker graphs | objective value | Helped |
| use the proposed algorithm instead of Udwani MWU and Saturate | fair centrality maximization · Amazon co-purchasing graphs | objective value | Helped |
| use the proposed algorithm instead of prior work | fair influence maximization · Antelope Valley, ethnicity | objective value | Helped |
| use the proposed algorithm instead of Saturate | multiobjective submodular maximization · max-k-cover, Erdős-Rényi graphs | objective value | Helped |
| increase the number of outer-loop repetitions (ablation) | LP Greedy · max-k-cover, Erdős-Rényi graphs | objective value | Helped |
| vary the greediness factor φ (ablation) | LP Greedy · max-k-cover, Erdős-Rényi graphs | objective value | Mixed |
| use Saturate instead of the proposed algorithm | fair influence maximization · Antelope Valley network, additional attributes | objective value | Helped |
Surprising findings
- On one fair influence maximization instance with small budget, the heuristic Saturate outperforms the proposed algorithm.
Limitations
- Requires budget B = Omega(k/eps^3 log k) for the guarantee.
- Approximation guarantee is 1-1/e-eps rather than exact 1-1/e and holds with probability 1-delta via repetitions.
- Uses 20 outer repetitions and a tuned greediness factor phi=10 in experiments, and omits the pre-processing step in experiments.
Experimental setup
Datasets: Kronecker graphs Erdős-Rényi graphs Barabási-Albert graphs Amazon co-purchasing networks Antelope Valley simulated network
Benchmarks: max-k-cover synthetic graphs Amazon co-purchasing fair centrality instances Antelope Valley fair influence maximization
Metrics: min-over-colors objective value number of function evaluations running time
Baselines: Udwani MWU Saturate Greedy Round Robin Greedy Minimum Continuous Frank-Wolfe for influence maximization
Builds on: greedy algorithm for submodular maximization Udwani multiobjective MWU Swap Rounding Saturate
Closest papers by meaning
- Instance Specific Approximations for Submodular Maximization (ICML 2021 · similarity 0.92)
- Multi-objective Maximization of Monotone Submodular Functions with Cardinality Constraint (NeurIPS 2018 · similarity 0.92)
- Breaking Barriers: Combinatorial Algorithms for Non-Monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation (ICML 2025 · similarity 0.90)
- Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint (NeurIPS 2024 · similarity 0.90)
- Consistent Submodular Maximization (ICML 2024 · similarity 0.90)
- Discretely beyond $1/e$: Guided Combinatorial Algortihms for Submodular Maximization (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.