# Niu et al. 2023 - Fast algorithms for k-submodular maximization subject to a matroid constraint

## One-paragraph Summary

Day la paper threshold-decreasing cho `k`-submodular maximization duoi matroid, mo rong huong fast threshold greedy tu size constraints sang mot rang buoc cau truc hon. Dong gop chinh la thay greedy co query complexity phu thuoc tuyen tinh vao rank `r` bang mot decreasing-threshold procedure chi mat them he so `log(r / epsilon) / epsilon`, trong khi van giu moc xap xi quen thuoc: `(1/2 - epsilon)` cho monotone va `(1/3 - epsilon)` cho non-monotone. Paper cung chi ra total-size constraint chi la mot corollary cua uniform matroid, nen ket qua nay noi truc tiep voi nhanh near-linear total-size da co trong repo.

## Classification Rationale

Paper thuoc `k-submodular` vi nghiem van la `k` tap roi nhau tren `(k+1)^E`. Diem moi cua no khong nam o model, ma o rang buoc `matroid` va muc tieu giam query complexity. Ve lineage, no noi giua:

- Sakaue 2017 va Sun et al. 2022 cho greedy matroid;
- Ohsaka-Yoshida / Nie et al. cho total-size;
- Badanidiyuru-Vondrak style thresholding cho submodular.

No khong phai paper streaming, nhung co cung DNA "threshold lam query complexity khong con phu thuoc tuyen tinh vao budget / rank".

## Setup

- Domain: `k`-submodular function `f : (k+1)^E -> R`.
- Constraint: support phai la mot independent set trong matroid `(E, F)` co rank `r`.
- Access model: value oracle cho `f` va independence oracle cho matroid.
- Objective classes: ca monotone va non-monotone.

## Main Results

1. Algorithm 1 dat `(1/2 - epsilon)` cho monotone matroid-constrained `k`-submodular maximization.
2. Cung algorithm dat `(1/3 - epsilon)` cho non-monotone case.
3. Query complexity la `O((n / epsilon) log(r / epsilon) * (k * EO + IO))`.
4. Tu uniform matroid suy ra corollary cho total-size constraint voi `O((nk / epsilon) log(B / epsilon))` queries va cung ratios tren.

## Core Algorithmic Idea

Thay vi moi vong lap tim phan tu / nhan tot nhat roi chen ngay nhu greedy chuan, paper duyet mot nguong `w` giam dan:

- Khoi tao `w` bang singleton gain lon nhat `d`.
- O moi muc nguong, quet cac phan tu feasible; voi moi `e`, chon nhan `i` co marginal gain lon nhat.
- Neu `Delta_{e,i} f(p) >= w` thi them `(e, i)` vao nghiem va cap nhat lai tap phan tu con feasible theo matroid.
- Giam `w` bang he so `(1 - epsilon)` cho den khi nho hon `((1 - epsilon) epsilon / (2r)) d`.

Y tuong la thresholding giu duoc gan-voi-greedy enough de xap xi khong mat nhieu, nhung tranh phai moi lan tim argmax toan cuc.

## Proof / Analysis Strategy

Proof dung mot transformed optimum `o_0, o_1, ..., o_t` dong bo voi sequence nghiem `p_0, ..., p_t` cua algorithm.

- Moi khi algorithm chon `(e_j, i_j)`, paper sua optimum bang cach bo mot phan tu `o_j` nhat dinh ra khoi support roi chen `e_j` vao, dung exchange property cua matroid de giu feasibility.
- Monotone case: moi buoc gia tri optimum giam khong qua `1 / (1 - epsilon)` lan gain cua nghiem threshold.
- Non-monotone case: do mat monotonicity, paper phai them mot nhan phu `i'` va dung pairwise monotonicity, nen he so thanh `(2 - epsilon) / (1 - epsilon)`.
- Tong qua cac vong lap cho lower bound tren `f(p_t)` theo `f(o)`.
- Neu algorithm dung som truoc khi du `r` phan tu, paper dung final threshold de chan phan marginal con lai cua optimum; neu chay du `r` buoc thi transformed optimum trung luon voi nghiem algorithm.

## Key Techniques

- decreasing-threshold procedure
- exchange-based transformation giua optimum va threshold solution
- matroid base exchange / feasible replacement
- threshold-to-greedy comparison with factor `1 / (1 - epsilon)`
- pairwise monotonicity de xu ly non-monotone

## Key Lemmas Or Structural Claims

- Claim 1: monotone per-step loss cua transformed optimum bi chan boi `1 / (1 - epsilon)` lan gain cua nghiem.
- Claim 2: non-monotone per-step loss bi chan boi `(2 - epsilon) / (1 - epsilon)` lan gain.
- Theorem 2: thu duoc `(1/2 - epsilon)` monotone va `(1/3 - epsilon)` non-monotone duoi total-size / matroid.
- Corollaries 1-2: uniform matroid dua ngay ve total-size thresholds.

## Delicate Points / Caveats

- Paper dung ky hieu "Theorem 2" de phat bieu ket qua chinh, nhung noi dung than paper qua lai giua total-size va matroid; can doc ky de thay matroid la setting goc, total-size la corollary.
- Query bound van co `IO` do phai cap nhat feasibility cua support, nen no khong "linear query" theo nghia chi dem value oracle.
- Ket qua ratio khong cai thien moc ly thuyet so voi greedy, ma cai thien efficiency.

## Extraction To Concepts

- Bo sung vao `concepts/k-submodularity.md` nhanh threshold-decreasing duoi matroid.
- Reusable ingredient: exchange-style proof spine cua greedy van song duoi thresholding neu moi cap `(e, i)` chi bi mat mot he so `1 - epsilon`.

## Extraction To Syntheses

- `syntheses/k-submodular.md` nen ghi ro nhanh `matroid + fast threshold`.
- Paper nay nen duoc dat gan Sakaue 2017 va Nie 2023 de thay su chuyen tu greedy / threshold duoi rang buoc matroid-size.

## Weaknesses / Limits

- Khong cho ket qua moi ve streaming hay fairness.
- Proof van rat gan greedy backbone cu, nen gia tri chinh la efficiency hon la approximation frontier.