# Metadata

- Title: Maximizing a k-Submodular Maximization Function under an Individual Knapsack Constraint
- Authors: Tan D. Tran, Canh V. Pham, Dung K. T. Ha
- Year: 2023
- Venue: Proceedings of the 12th International Symposium on Information and Communication Technology (SoICT 2023)
- Primary group: k-submodular
- Secondary tags: monotone, individual-knapsack, streaming, thresholding, conference-version
- Problem: monotone k-submodular maximization under individual knapsack constraints, where each label/source has its own budget
- Main guarantee: first streaming approximation paper in the repo for individual-knapsack k-submodular maximization, with a two-loop streaming algorithm of query complexity O(nk log(B) / epsilon) and approximation factor written in the paper as 2(k+1)/(1-epsilon)
- Key techniques: opt-known streaming template, geometric guessing of the optimum, per-label budget feasibility checks, threshold acceptance with best singleton fallback
- Status: processed-deep
- Tags: #k-submodular #individual-knapsack #streaming #thresholding #conference-version
- Inbox source: inbox/2. k-sub.pdf