# Metadata

- Title: Streaming Algorithms for the k-Submodular Cover Problem
- Authors: Wenqi Wang, Gregory Gutin, Yaping Mao, Donglei Du, Xiaoyan Zhang
- Year: 2023
- Venue: arXiv preprint, December 6, 2023; journal venue to verify
- Primary group: k-submodular
- Secondary tags: cover, streaming, bicriteria, weighted, monotone, non-monotone
- Problem: weighted k-submodular cover in the streaming model, seeking low cost while reaching a target utility threshold
- Main guarantee: develops known-optimum, two-pass, and one-pass streaming bicriteria algorithms; the two-pass algorithm achieves `( (3 - epsilon) / (2 epsilon (1 - epsilon)), (1 - epsilon) / 2 )` in the monotone case and `( (4 - epsilon) / (3 epsilon (1 - epsilon)), (1 - epsilon) / 3 )` in the non-monotone case, with one-pass guarantees of the same qualitative form
- Key techniques: thresholding by utility-per-cost under an upper-cost budget, handling big singleton elements separately, geometric guessing of the optimal cover cost, and dynamic guess maintenance for one-pass streaming
- Status: processed-deep; venue-year-to-verify
- Tags: #k-submodular #cover #streaming #bicriteria #weighted
- Inbox source: inbox/2312.03593v1.pdf