# Zheng et al. 2021 - Maximizing Approximately k-Submodular Functions

## One-paragraph Summary

Day la paper "robustness / noisy objective" cho `k`-submodular maximization. Thay vi gia su ham muc tieu la `k`-submodular chinh xac, paper hoi dieu gi xay ra neu objective chi gan `k`-submodular. Tac gia dua ra hai dinh nghia:

- `eps`-approximately k-submodular (`eps`-AS);
- `eps`-approximately diminishing returns (`eps`-ADR).

Sau do paper chay lai greedy analyses cua Ohsaka-Yoshida cho total-size va individual-size constraints, nhung them slack nhan theo `eps`. Ket qua la mot bo ratio giam mem theo do lech khoi exact `k`-submodularity. Diem hay nhat cua paper la cho thay neu co mot exact proxy `f` nam ke sat objective `F`, thi giai bai toan tren `f` roi chuyen guarantee sang `F` cho ket qua sach hon va tot hon viec greedy truc tiep tren `F`.

## Setup

- Domain: `F : (k + 1)^V -> R_+`.
- Constraints:
  - total size `sum_i |X_i| <= B`;
  - individual size `|X_i| <= B_i`.
- Hai notion moi:
  - `eps`-AS: bat dang thuc `k`-submodular chi dung len den he so nhan `(1 +- eps)`;
  - `eps`-ADR: cac marginal gains thoa diminishing returns voi multiplicative slack.
- Paper cung xet truong hop ton tai ham `k`-submodular chinh xac `f` sao cho `(1 - eps) f(x) <= F(x) <= (1 + eps) f(x)`.

## Main Results

1. `eps`-ADR keo theo `eps`-AS, nhung chieu nguoc lai khong dung.
2. Tong-size, greedy truc tiep tren `F`:
  - neu `F` la `eps`-AS thi ratio la `((1 - eps)^2) / (2 (1 - eps + eps B) (1 + eps))`;
  - neu `F` la `eps`-ADR thi ratio la `(1 - eps) / 2`.
3. Individual-size, greedy truc tiep tren `F`:
  - neu `F` la `eps`-AS thi ratio la `((1 - eps)^2) / ((3 - 3 eps + 2 eps B) (1 + eps))`;
  - neu `F` la `eps`-ADR thi ratio la `(1 - eps) / (3 + eps)`.
4. Transfer theorem: neu `f` la ham `k`-submodular exact ke sat `F`, bat ky `alpha`-approximation cho `f` se cho `(1 - eps) alpha / (1 + eps)`-approximation cho `F`.

## Core Algorithmic Idea

Thuật toan thuc ra khong moi: paper dung lai hai greedy quen thuoc cua Ohsaka-Yoshida:

- `k-Greedy-TS` cho total-size;
- `k-Greedy-IS` cho individual-size.

Moi vong lap, greedy chon cap `(e, i)` co marginal gain lon nhat trong cac cap feasible. Diem moi nam o phan tich:

- neu objective chi xap xi `k`-submodular, moi inequality trong proof greedy phai cho phep mat mot he so nhan;
- `eps`-ADR giu duoc control tren local marginals tot hon, nen cho ratio dep hon `eps`-AS;
- neu ton tai exact proxy `f`, thay vi chiu slack o moi buoc greedy, ta gop toan bo sai so vao mot transfer step cuoi cung.

## Proof / Analysis Strategy

- Phan structural: chung minh `eps`-ADR => `eps`-AS va xay counterexample cho chieu nguoc lai.
- Phan greedy: mo phong proof exact `1 / 2` va `1 / 3`, nhung o moi buoc chuyen marginal cua optimum ve nghiem greedy partial phai chen he so slack `1 +- eps`.
- Phan transfer: neu `S_f` la `alpha`-approximation cho `f` thi
  `F(S_f) >= (1 - eps) f(S_f) >= (1 - eps) alpha f(OPT_f) >= ((1 - eps) alpha / (1 + eps)) F(OPT_F)`.

## Key Techniques

- multiplicative relaxation cua `k`-submodularity
- relation giua approximate DR va approximate `k`-submodularity
- perturbation analysis cua greedy
- exact-proxy transfer lemma

## Delicate Points / Caveats

- Ratio `eps`-AS degrade theo tong budget `B`, trong khi `eps`-ADR dep hon nhieu.
- Paper chi xu ly size constraints, khong xu ly knapsack hay matroid.
- Dinh nghia approximate o day mang tinh worst-case multiplicative, khong phai stochastic noise model.

## Extraction To Concepts

- Nen tao concept note rieng `concepts/approximate-k-submodularity.md`.

## Extraction To Syntheses

- `syntheses/k-submodular.md` nen them paper nay vao huong "approximate / noisy objective".

## Weaknesses / Limits

- Khong dua ra thuat toan moi ngoai greedy co san.
- Chua co ket qua cho matroid / knapsack / streaming.