# Zhu et al. 2024 - Fairness in Monotone k-submodular Maximization: Algorithms and Applications

## One-paragraph Summary

Day la paper fairness dau tien trong repo cho `k`-submodular maximization. Bai toan khong chi co tong budget `B`, ma con ap lower / upper bounds cho so phan tu mang moi nhan. Paper cho thay fairness khong buoc phai lam mat moc ly thuyet co ban: greedy fairness-aware van dat `1/3`, bang voi best-known ratio cho individual-size constrained line, va threshold version dat `(1/3 - epsilon)` voi query complexity chi logarithmic theo `B`. Ngoai ra, paper con xet tinh huong chi co approximate oracle va dua ra guarantees giam theo `delta`.

## Classification Rationale

Paper thuoc `k-submodular` vi fairness duoc ap tren cac nhan cua `k`-set. No mo ra mot nhanh moi trong repo:

- size / budget constraints + fairness lower-upper quotas;
- monotone objective;
- threshold speeding up fairness-aware greedy.

No ket noi tu nhien voi papers ve influence maximization `k` topics va sensor placement `k` types.

## Setup

- Objective: monotone `k`-submodular maximization.
- Constraints:
  - tong so phan tu chon khong qua `B`;
  - moi nhan `i` phai thoa `l_i <= |X_i| <= u_i`.
- Paper goi mot partial solution la `extendable` neu no van co the duoc mo rong thanh nghiem fairness-feasible.
- Co them model approximate oracle `tilde f` la `delta`-approximate so voi `f`.

## Main Results

1. `Fair-Greedy` dat `1/3`-approximation trong `O(knB)` oracle evaluations.
2. `Fair-Threshold` dat `(1/3 - epsilon)` trong `O((kn / epsilon) log(B / epsilon))`.
3. Voi approximate oracle:
   - Greedy co guarantee giam theo `delta`, cu the la `((1 - delta) / (3 + 2B((1 + delta)/(1 - delta) - 1)))`;
   - Threshold co guarantee tuong tu, them phu thuoc `epsilon`.
4. Thuc nghiem cho thay fairness khong lam giam chat luong nghiem qua manh tren influence maximization va sensor placement.

## Core Algorithmic Idea

Paper dua vao notion `extendable`.

- `Fair-Greedy`: moi vong chon cap `(e, i)` co marginal gain lon nhat trong tap cac cap ma neu chen vao thi partial solution van extendable. Do do algorithm khong tu dong bi ket o cuoi do vi da "lam day sai nhan".
- `Fair-Threshold`: dung priority queue tren cac cap `(e, i)` voi priority la marginal gain, ket hop lazy re-evaluation va thresholding. Cap nao khong con du gain se bi giam priority; cap nao khong con extendable se bi bo.

Noi cach khac, fairness constraint duoc dua thang vao predicate feasibility cua tung buoc greedy.

## Proof / Analysis Strategy

- Paper sua backbone `o_j` / `s_j` quen thuoc trong `k`-submodular greedy proof de hop voi fairness.
- Kho khan chinh la `Q_i^j` co the rong vi lower / upper bounds bat doi xung, nen paper phai chung minh luon ton tai mot nhan `c` con du cho exchange khi `Q_{i_j}^j` rong.
- Lemma 4 cho thay moi buoc gain cua greedy it nhat bang mot nua loss cua transformed optimum; tong qua `B` buoc cho ra `1/3`.
- Threshold version dung cung transformation, nhung moi cap duoc them vao chi can dat `(1 - epsilon)` lan upper bound cua ung vien khac, nen he so proof doi thanh `(1 - epsilon) / 2`, tu do ra `(1/3 - epsilon)`.
- Approximate-oracle versions thay inequality exact bang dang suy giam boi he so `((1 + delta)/(1 - delta))`.

## Key Techniques

- extendability characterization cho fairness
- fairness-aware greedy under lower and upper quotas
- transformed-optimum charging adapted to fairness
- lazy thresholding with priority queue
- approximate-oracle robustness

## Key Lemmas Or Structural Claims

- Theorem 2: `Fair-Greedy` dat `1/3` trong `O(knB)`.
- Lemma 3: neu nhan greedy muon chen vao ma residual cua nhan do rong, luon co mot nhan khac cho exchange va cap do van extendable.
- Lemma 4: moi buoc gain cua greedy tra duoc it nhat mot nua loss cua transformed optimum.
- Theorem 6: `Fair-Threshold` dat `(1/3 - epsilon)` trong `O((kn / epsilon) log(B / epsilon))`.
- Theorem 5 va 9: phien ban approximate-oracle cho greedy va threshold.

## Delicate Points / Caveats

- Paper chi xu ly monotone objective.
- Guarantee fairness la exact theo lower va upper bounds, nhung chi duoi total budget; khong co matroid.
- Approximate-oracle guarantees co phu thuoc vao `B`, nen suy giam kha nhanh neu budget lon va `delta` khong nho.

## Extraction To Concepts

- Nen tao concept note rieng cho `fair-k-submodular-maximization`, vi paper nay va mot paper matroid moi trong inbox cung thuoc nhanh nay.
- `concepts/k-submodularity.md` nen co them mot nut fairness / extendability.

## Extraction To Syntheses

- `syntheses/k-submodular.md` nen them fairness nhu mot main problem setting rieng.
- Paper nay la entry point fairness de so sanh voi matroid fair paper moi.

## Weaknesses / Limits

- Chi monotone va chi total-budget.
- Proof technique rat greedy-centric; chua ro no mo rong den non-monotone matroid duoc den muc nao.