# Tran et al. 2023 - Improved Streaming Algorithm for Minimum Cost Submodular Cover Problem

## One-paragraph Summary

Day la paper cover rat hop voi repo nay vi no danh trung vao `minimum cost submodular cover` trong che do streaming. Muc tieu cua paper la cai thien dong thuat toan streaming truoc do von bi phu thuoc xau vao `c_min` hay chi xu ly duoc uni-cost. Ket qua chinh la `StrMSC`, mot multi-pass streaming algorithm tra ve `(1/epsilon, 1 - epsilon)`-bicriteria approximation voi query complexity near-linear theo `n`, nham dua MSC gan hon voi setting du lieu lon.

## Classification Rationale

Paper thuoc `submodular` va nam ro trong nhanh `cover`. No khac voi cac paper maximization do bai toan la toi thieu hoa cost de vuot mot threshold utility, nhung lai rat lien quan den lineage `Bar-Ilan -> Iyer-Bilmes -> Soma-Yoshida` trong repo.

## Setup

- Domain / model: monotone submodular utility `f : 2^V -> R_+`, additive cost `c`, target `T`.
- Oracle / access model: value oracle cho `f`.
- Objective: tim tap `S` co cost nho nhat sao cho `f(S) >= T`.
- Guarantee type: bicriteria, tuc cho phep cost va muc cover deu xap xi trong cung mot theorem.

## Main Results

1. Paper dua ra `StrMSC`, mot streaming algorithm cho MSC co `(1/epsilon, 1 - epsilon)`-bicriteria approximation.
2. Query complexity la near-linear theo `n` va so passes chi o muc logarithmic, danh vao yeu diem cua cac thu tuc cu phu thuoc vao `1 / c_min` hay `opt / c_min`.
3. Thuc nghiem tren Revenue Threshold va Coverage Threshold cho thay `StrMSC` tot hon MULTI / SINGLE cua Crawford et al. va canh tranh voi greedy khong streaming.

## Core Algorithmic Idea

Paper co hai y tuong cot loi.

Thu nhat, no tach mot tap `V_0` gom cac phan tu co cost rat nho. Muc dich khong phai de lay nghiem truc tiep, ma de cat bo su phu thuoc xau vao `c_min`; sau khi remove `V_0`, ratio cost trong phan con lai du de chay thresholding multi-pass voi query near-linear.

Thu hai, tren phan con lai, paper quet qua mot day thresholds hinh hoc. O moi pass, no thu xay candidate bang cach them cac phan tu co marginal-per-cost vuot nguong va dung lai khi dat muc cover can thiet. Cuoi cung no so sanh candidate "co V_0" va "khong co V_0" de lay nghiem cost tot hon.

## Proof / Analysis Strategy

- Buoc 1: chung minh viec boc tach `V_0` khong lam hong bai toan, ma chi giup khoa ratio cost va do do khoa duoc query complexity.
- Buoc 2: voi mot guess / threshold phu hop, candidate xay boi thresholding dat muc utility `(1 - epsilon) T`.
- Buoc 3: nhan threshold dung de chi ra cost cua candidate bi chan boi `O(1/epsilon)` lan optimum.
- Buoc 4: cong don so passes / queries qua luoi thresholds va pha tach `V_0` de ra complexity near-linear.

## Key Techniques

- bicriteria approximation cho cover
- tach cac phan tu tiny-cost de giam phu thuoc vao `c_min`
- thresholding theo marginal-per-cost
- multi-pass streaming thay vi single-pass
- so sanh nghiem co / khong co `V_0`

## Key Lemmas Or Structural Claims

- Sau khi tach `V_0`, pham vi cost duoc kiem soat du de threshold schedule chi can logarithmic so passes.
- O mot threshold dung, candidate se vuot duoc `(1 - epsilon) T`.
- Cost cua candidate dat nguong nay khong qua `1/epsilon` lan optimum up to constants tu phan tich.

## Delicate Points / Caveats

- Theorem la bicriteria, khong phai exact cover guarantee. Day la cai gia phai tra de co streaming near-linear.
- Paper xu ly monotone MSC; khong phai setting general non-monotone cover.
- Phan trinh bay OCR cua file intake hoi vo, nhung spine cua thuat toan van ro: tach `V_0`, threshold schedule, chon candidate tot nhat.

## Extraction To Concepts

- Day la ly do tot de tao `concepts/submodular-cover.md`.
- Technique lap lai: threshold marginal-per-cost cho cover / budgeted settings.
- Quan he voi nhom khac: la mot moc streaming trong cover lineage cua repo.

## Extraction To Syntheses

- Cap nhat `syntheses/submodular.md` trong nhanh cover va streaming.
- Lien ket voi 1998 general cover, 2013 submodular cover + knapsack, va 2015 DR generalized cover.

## Weaknesses / Limits

- Bicriteria guarantee van yeu hon greedy exact-style neu khong bi ep boi streaming.
- Multi-pass, nen chua phai streaming mot pass.
- Paper giai quyet MSC monotone, khong bao phu het cac cover variants trong van hoc.

## Research Ideas Triggered

- Tao comparison note rieng cho cover lineage trong repo.
- Kiem tra xem tach `V_0` co the chuyen sang integer-lattice / DR cover hay khong.