# Metadata

- Title: Fast Streaming Algorithms for k-Submodular Maximization under a Knapsack Constraint
- Authors: Canh V. Pham, Dung K.T. Ha, Huan X. Hoang, Tan D. Tran
- Year: 2022
- Venue: Proceedings of the 2022 IEEE 9th International Conference on Data Science and Advanced Analytics (DSAA)
- Primary group: k-submodular
- Secondary tags: monotone, knapsack, streaming, deterministic, thresholding, query-efficient
- Problem: monotone k-submodular maximization under a single knapsack constraint in the value-oracle / streaming setting
- Main guarantee: first constant-factor streaming algorithms in the repo for k-submodular knapsack maximization with linear query complexity, namely a single-pass 1/10 approximation in O(nk) queries and a multi-pass (1/4 - epsilon) approximation in O(nk/epsilon) queries
- Key techniques: heavy-vs-light cost partition, cost-normalized marginal thresholding, suffix truncation to restore feasibility, geometric threshold guessing from a coarse constant-factor lower bound
- Status: processed-deep
- Tags: #k-submodular #knapsack #streaming #maximization #thresholding #deterministic
- Inbox source: inbox/IEEE_DSAA22_Final_tantd.zip; extracted source in inbox/IEEE_DSAA22_Final_tantd/