# Metadata

- Title: Online and Streaming Algorithms for Constrained k-Submodular Maximization
- Authors: Fabian Christian Spaeh, Alina Ene, Huy Nguyen
- Year: 2025
- Venue: AAAI 2025; inbox file is the 2023 arXiv preprint
- Primary group: k-submodular
- Secondary tags: monotone, non-monotone, online, streaming, cardinality, knapsack, partition-matroid, primal-dual
- Problem: online and streaming algorithms for constrained k-submodular maximization under cardinality and knapsack constraints, with additional partition-matroid submodular corollaries
- Main guarantee: unifies single-pass online/streaming algorithms for constrained k-submodular maximization; for monotone cardinality constraints the guarantee improves from `1/4` to about `0.3178` as the minimum budget grows, for general cardinality constraints it is at least `1/8` and tends to about `0.1589`, and the appendix gives the first constant-factor guarantees for individual knapsack constraints when item sizes are small relative to the budgets
- Key techniques: threshold-based online allocation with part-specific coefficients, primal/dual potential comparison, handling imbalanced budgets via part-wise parameter tuning, non-monotone extensions through pairwise-monotonicity-aware adaptations and a two-solution reduction
- Status: processed-deep
- Tags: #k-submodular #online #streaming #cardinality #knapsack #non-monotone #AAAI
- Inbox source: inbox/2305.16013v1.pdf