# Metadata

- Title: Streaming Algorithm for Monotone k-Submodular Maximization with Cardinality Constraints
- Authors: Alina Ene, Huy L. Nguyen
- Year: 2022
- Venue: Proceedings of the 39th International Conference on Machine Learning (ICML 2022), PMLR 162
- Primary group: k-submodular
- Secondary tags: monotone, streaming, online, cardinality, per-coordinate-budgets, primal-dual
- Problem: monotone k-submodular maximization under per-coordinate cardinality constraints `|S_i| <= B_i` in the streaming / online with free disposal setting
- Main guarantee: single-pass combinatorial primal-dual algorithm using `O(k|V|)` value-oracle calls and `O(sum_i B_i)` space, with approximation `1 / (2(1 + B(2^(1/B) - 1)))` where `B = min_i B_i`; this is at least `1/4` and approaches `1 / (2(1 + ln 2)) ~= 0.2953` as `B` grows
- Key techniques: primal-dual LP viewpoint, dynamically increasing per-label thresholds, keeping only a single feasible solution, deque-based eviction of the earliest element when a budget is exceeded
- Status: processed-deep
- Tags: #k-submodular #streaming #online #cardinality #primal-dual #monotone
- Inbox source: inbox/ene22a.pdf