# Metadata

- Title: Improved Streaming Algorithm for Minimum Cost Submodular Cover Problem
- Authors: Tan D. Tran, Canh V. Pham, Dung P. Trung, Uyen T. Nguyen
- Year: 2023
- Venue: Computational Data and Social Networks - 12th International Conference, CSoNet 2023 (LNCS 14479, Springer)
- Primary group: submodular
- Secondary tags: cover, minimum-cost, bicriteria, streaming, multi-pass
- Problem: minimum cost submodular cover for monotone submodular utility with additive costs and threshold target
- Main guarantee: proposes StrMSC, a multi-pass streaming algorithm with near-linear query complexity that returns a (1/epsilon, 1 - epsilon)-bicriteria approximation for minimum cost submodular cover
- Key techniques: cost sorting, carving out tiny-cost elements to control the c_min dependence, geometric threshold passes, bicriteria stopping rule
- Status: processed-deep
- Tags: #submodular #cover #minimum-cost #bicriteria #streaming
- Inbox source: inbox/3. SMC.pdf