# Metadata

- Title: k-Submodular Maximization Under Individual Knapsack Constraints: Applications and Streaming Algorithm
- Authors: Tan D. Tran, Canh V. Pham, Dung T. K. Ha
- Year: 2025
- Venue: Asia-Pacific Journal of Operational Research (APJOR)
- Primary group: k-submodular
- Secondary tags: monotone, non-monotone, individual-knapsack, streaming, journal-extension
- Problem: k-submodular maximization under individual knapsack constraints in the streaming model
- Main guarantee: proposes Str, a deterministic two-pass streaming algorithm with O(Bk log(n) / epsilon) query complexity and O(B log(n) / epsilon) space complexity, achieving approximation factor written in the paper as 2(k+1)/(1-epsilon) for monotone objectives and 2k+3 for non-monotone objectives
- Key techniques: opt-known streaming subroutine StrOpt, geometric guessing over the optimum, threshold acceptance per label-budget, extension from monotone to non-monotone via pairwise monotonicity reasoning
- Status: processed-deep
- Tags: #k-submodular #individual-knapsack #streaming #non-monotone #journal-extension
- Inbox source: inbox/5. k-sub apjor.pdf