# Wang et al. 2023 - Streaming Algorithms for the k-Submodular Cover Problem

## One-paragraph Summary

Day la paper cover-side cho `k`-submodular functions, doi ung voi nhanh maximization da rat day trong repo. Bai toan dat ra la tim mot nghiem cost nho nhat sao cho utility `g(x)` dat moc `tau`, trong che do streaming. Paper dua ra ba lop thuat toan: mot threshold algorithm gia su biet cost optimum, mot bien the 2-pass de bo gia su do bang geometric guesses, va mot bien the 1-pass de duy tri guesses dong. Diem can nho la ket qua la bicriteria: cost chi duoc xap xi trong he so `O(1 / epsilon)` va utility dat mot ti le hang so cua `tau`, cu the `(1 - epsilon) / 2` cho monotone va `(1 - epsilon) / 3` cho non-monotone.

## Classification Rationale

Paper thuoc `k-submodular` vi objective la `k`-submodular cover, nhung no cung mo mot huong moi trong repo: cover tren assignment domain, song song voi `submodular cover` va `DR-submodular cover`. Vi vay no la mot paper giao thao tot giua nhanh `k-submodular` va `cover lineage`.

## Setup

- Objective: weighted `k`-submodular cover.
- Input: ground set `X`, utility `g`, target `tau`, weight function `w`.
- Goal: tim nghiem `x` co cost thap trong khi `g(x) >= tau`.
- Model: streaming, voi nhu cau bo nho han che va query per element thap.
- Objective classes: paper xu ly ca monotone va non-monotone.

## Main Results

1. Algorithm 1 (biet mot guess cost optimum `w(v)`) tra ve:
   - monotone: cost `<= ((3 - epsilon) / (2 epsilon)) w(v)` va utility `>= (1 - epsilon) tau / 2`;
   - non-monotone: cost `<= ((4 - epsilon) / (3 epsilon)) w(v)` va utility `>= (1 - epsilon) tau / 3`.
2. Algorithm 2 (2-pass) bo gia su biet optimum bang geometric guesses:
   - monotone: `( (3 - epsilon) / (2 epsilon (1 - epsilon)), (1 - epsilon) / 2 )` bicriteria;
   - non-monotone: `( (4 - epsilon) / (3 epsilon (1 - epsilon)), (1 - epsilon) / 3 )` bicriteria.
3. Algorithm 3 (1-pass) giu cung muc utility target xap xi, trong khi duy tri bo guesses dong tu upper bound `B`.
4. Bo nho va query-per-element chi logarithmic theo guess range, nen paper thuc su huu ich cho cover streaming.

## Core Algorithmic Idea

Khung cua paper la threshold cover streaming.

- Neu gap mot "big element" co the mot minh dat utility threshold, giu no nhu singleton candidate.
- Neu khong, paper duy tri mot nghiem `x` va chen phan tu khi marginal gain theo utility vuot nguong ty le voi cost.
- Biet optimum cost thi nguong va upper-cost budget `A` duoc dat thang.
- Khong biet optimum thi:
  - Algorithm 2 quet 2 pass de tao geometric guess set `Lambda`;
  - Algorithm 3 duy tri lower / upper bounds dong (`L`, `U`) va chay nhieu instance guesses song song.

Noi ngan gon, day la "guessed-opt threshold streaming" cho cover, thay vi guessed-opt thresholding cho maximization.

## Proof / Analysis Strategy

Phan tich chay quanh mot optimum `v` cua bai toan cover.

- Lemma 2 tach truong hop nghiem output co chua mot big element hay khong.
- Lemma 3 / 4 dung orthant-submodularity va residual optimum argument de chan utility cua nghiem stream.
- Theorem 2 khoa bicriteria guarantee trong truong hop biet `w(v)`.
- Theorem 3 va 4 cho thay geometric guesses va dynamic guesses giu duoc nghiem co cost trong he so them `1 / (1 - epsilon)`.
- Paper cung nhac toi conversion theorem tu bicriteria cover sang unconstrained maximization, dung de dat lower-bound intuition cho tai sao he so utility `(1 - epsilon) / 3` la hop ly cho deterministic non-monotone line.

## Key Techniques

- threshold theo utility-per-cost
- tach "big element" singleton
- known-optimum guessed-cost template
- geometric guess grid cho 2-pass streaming
- dynamic guess interval cho 1-pass streaming
- bicriteria cover analysis

## Key Lemmas Or Structural Claims

- Theorem 2: known-guess streaming template cho weighted `k`-submodular cover.
- Theorem 3: 2-pass version voi guess set `Lambda`.
- Theorem 4: 1-pass version voi dynamic guesses.
- Monotone / non-monotone utility guarantees la `(1 - epsilon) tau / 2` va `(1 - epsilon) tau / 3`.

## Delicate Points / Caveats

- Day la paper cover, khong phai maximization; khi dua vao synthesis can tach ro khoi unconstrained / constrained maximization.
- Guarantee la bicriteria, nen cost va utility deu bi noi gian; khong nen doc nham no nhu mot exact cover approximation ratio duy nhat.
- Ky hieu trong paper dung `w(v)` cho optimum cost, de nham voi utility neu doc qua nhanh.

## Extraction To Concepts

- Chua can tao concept file rieng, nhung nen bo sung vao `concepts/k-submodularity.md` mot nut cover / bicriteria streaming.
- Ve retrieval, paper nay la moc de so sanh voi `submodular-cover.md` va `dr-submodularity-on-integer-lattice.md`.

## Extraction To Syntheses

- `syntheses/k-submodular.md` nen co them problem setting `cover`.
- Open direction tu nhien: cover-to-max relation tren `k`-submodular co the sau hon nhung gi paper nay moi dung o muc lower-bound / conversion theorem.

## Weaknesses / Limits

- Ratios utility cho non-monotone van yeu hon line maximization.
- Paper streaming cover nay chua ket noi truc tiep voi fairness hay matroid settings.