Research map / Learning theory and algorithms / Submodular and game algorithms
Online and Streaming Algorithms for Constrained k-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.
Gives single-pass online and streaming algorithms with improved constant-factor approximations for constrained k-submodular maximization (monotone and non-monotone) under cardinality and knapsack constraints, evaluated on ad allocation, influence maximization, and max-k-cut.
Problem
Maximizing k-submodular functions under individual cardinality or knapsack budget constraints in the online and streaming settings, where data is large and decisions must be made immediately.
Approach
A primal-dual threshold algorithm where each part's threshold is a carefully designed exponential-weighted linear combination of marginal gains of only the currently allocated items, analyzed via a local primal/dual argument; extended to non-monotone objectives via a modified part-selection rule and a two-solution scheme for large budgets.
Key results
- For monotone objectives with cardinality constraints, the online/streaming algorithm guarantees approximation about 0.3178 as minimum budget tends to infinity, improving on 0.2953 of Ene and Nguyen 2022.
- For general (non-monotone) k-submodular maximization, the paper gives the first constant-factor online/streaming guarantee, about 0.1589 as minimum budget grows.
- On ad allocation, the modified-parameter algorithms match or outperform offline greedy on the Yahoo and iPinYou instances while using far fewer function evaluations; on imbalanced iPinYou budgets Algorithm 1 reaches 10236 vs 10428 for offline greedy.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the proposed Algorithm 1 instead of Ene and Nguyen (2022) | online and streaming monotone k-submodular maximization · cardinality constraints | approximation ratio: ≥1/4 -> ≈0.3178 as n → ∞ | Helped |
| use the proposed Algorithm 2 for general objectives | online and streaming k-submodular maximization · cardinality constraints, general objectives | approximation ratio: ≥1/8; ≈0.1589 as n → ∞ | Helped |
| reduce each ca to 1/4 of the theoretical choice (ablation) | Algorithm 1 · iPinYou ad allocation, imbalanced budgets | function value: 7499.13 ± 68.22 -> 10236.05 ± 220.22 | Helped |
| use modified rather than theoretical parameter choices (ablation) | Ene and Nguyen (2022) · iPinYou ad allocation, imbalanced budgets | function value: 5698.33 ± 88.57 -> 9681.85 ± 152.87 | Helped |
| use Algorithm 1 with modified parameter choices instead of offline greedy | iPinYou ad allocation · ad allocation instances | function value | Mixed |
| use the proposed online algorithms instead of offline greedy | monotone k-submodular maximization · influence maximization and max-k-cut | function value: about 8% | Hurt |
Surprising findings
- With modified (less conservative) parameters, the online algorithms match or even outperform offline greedy on ad allocation instances despite the greedy being offline.
Limitations
- Non-monotone guarantees are constant but small (about 0.1589 asymptotically), and the approximation depends on the minimum budget being large.
- Theoretical parameter choices are conservative; practical gains required modified parameters that lack theoretical guarantees.
- Experiments do not report approximation ratios, only comparisons to offline greedy heuristics on NP-hard instances.
Experimental setup
Datasets: iPinYou ad exchange Yahoo ad dataset Email network (Leskovec and Krevl 2014) influence maximization instances following Ene and Nguyen 2022
Benchmarks: iPinYou ad allocation Yahoo ad allocation influence maximization Email max-k-cut
Metrics: objective function value number of function evaluations approximation ratio guarantee
Baselines: Offline Greedy (Ohsaka and Yoshida 2015) Ene and Nguyen 2022 Xiao et al. 2022 greedy
Builds on: Ene and Nguyen 2022 online k-submodular algorithm Feldman et al. 2009 primal-dual online allocation Feldman, Karbasi, Kazemi 2018 subsampling for matchoid constraints Xiao et al. 2022 greedy for general k-submodular
Closest papers by meaning
- Streaming Algorithm for Monotone k-Submodular Maximization with Cardinality Constraints (ICML 2022 · similarity 0.94)
- Deletion-Robust Submodular Maximization with Knapsack Constraints (AAAI 2024 · similarity 0.94)
- Streaming Stochastic Submodular Maximization with On-Demand User Requests (NeurIPS 2025 · similarity 0.91)
- Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint (NeurIPS 2024 · similarity 0.90)
- Consistent Submodular Maximization (ICML 2024 · similarity 0.89)
- Online Two-Stage Submodular Maximization (NeurIPS 2025 · similarity 0.89)
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.