# Iwata, Tanigawa, Yoshida 2015 - Improved Approximation Algorithms for k-Submodular Function Maximization

## One-paragraph Summary

Day la paper cot loi cua nhanh `k`-submodular maximization. No nang moc unconstrained tu phan tich Ward-Zivny len `1 / 2`, dung bang moc tight quen thuoc cua submodular unconstrained maximization, va dong thoi cho monotone case mot thuat toan dat `k / (2k - 1)`. Quan trong hon, paper dong goi ro hai thuoc tinh cuc bo "orthant submodularity + pairwise monotonicity" thanh cong cu phan tich, roi dung doi xung oracle-dependence de chi ra rang monotone ratio do la asymptotically tight.

## Setup

- Domain: `f : {0, ..., k}^V -> R_+`, tuong duong mot `k`-subpartition cua `V`.
- Hai tinh chat local:
  - orthant submodularity;
  - pairwise monotonicity.
- Theorem 1.1 cua Ward-Zivny duoc dung nhu characterization cua `k`-submodularity.

## Main Results

1. Theorem 2.3:
   Algorithm 2 dat `E[f(s)] >= (1 / 2) f(o)` cho moi nonnegative `k`-submodular function.
2. Monotone case:
   co mot thuat toan randomized dat `k / (2k - 1)`.
3. Hardness:
   voi moi `eps > 0`, mot `((k + 1) / (2k) + eps)`-approximation cho monotone `k`-submodular maximization can exponentially many value queries.
4. Skew-bisubmodular extension:
   phan tich greedy theo tham so `alpha`, dat `2 sqrt(alpha) / (1 + sqrt(alpha))^2`, va ket hop them mot routine don gian de dam bao it nhat `8 / 25`.

## Core Algorithmic Idea

### Non-monotone unconstrained

- Xu ly tung phan tu `e` theo thu tu tuy y.
- Tinh marginal gains `y_i = Delta_{e,i} f(s)` cho cac nhan.
- Sap xep `y_i` giam dan va chon phan phoi gan nhan:
  - neu chi co mot marginal duong, gan tat vao nhan do;
  - neu co hai marginal duong, chon theo ty le `y_1 : y_2`;
  - neu co nhieu hon hai marginal duong, dung phan phoi geometric.
- Day la thay doi chinh so voi Ward-Zivny: phan phoi geometric cho phep can bang tot hon giua "mat cua optimum" va "lai cua thuat toan".

### Monotone

- Van theo khung randomized greedy tung phan tu.
- Xac suat chon nhan `i` ty le voi `y_i^(k-1)`.
- Lua chon nay khop dung bat dang thuc can thiet de dua he so `c = 1 - 1 / k` vao lemma one-step, tu do suy ra ratio `1 / (1 + c) = k / (2k - 1)`.

## Proof / Analysis Strategy

- Duy tri nghiem toi uu `o(j)` da "thay" cac quyet dinh ma thuat toan da lam cho `j` phan tu dau.
- O moi buoc, so sanh:
  - phan giam cua `f(o(j-1)) - f(o(j))`;
  - phan tang cua `f(s(j)) - f(s(j-1))`.
- Lemma 2.2 cho meta-condition: chi can chon phan phoi `p_i` sao cho expected loss cua optimum bi chan boi `c` lan expected gain cua thuat toan.
- Toan bo paper xoay quanh viec tim phan phoi `p_i` thoa condition do:
  - geometric distribution cho non-monotone `c = 1`;
  - power distribution `y_i^(k-1)` cho monotone `c = 1 - 1 / k`.
- Lower bound cho monotone case dung symmetry-gap / value-oracle construction theo kieu Feige-Mirrokni-Vondrak.

## Key Techniques

- randomized greedy tren assignment domain
- local one-step exchange inequality
- orthant submodularity + pairwise monotonicity
- geometric probability rule
- power-law probability rule cho monotone case
- value-oracle hardness qua doi xung

## Delicate Points / Caveats

- Ratio `1 / 2` o day la cho unconstrained nonnegative case; rang buoc matroid, knapsack, streaming, size constraints deu can machinery rieng o cac paper sau.
- Monotone algorithm van randomized; Oshima 2017 moi derandomize duoc ratio nay.
- Hardness paper danh vao monotone unconstrained case, nen bat ky mo rong ratio cho setting rang buoc can rat can than.

## Extraction To Concepts

- `concepts/k-submodularity.md` nen co ro:
  - paper nay la moc `1 / 2` cho unconstrained;
  - `k / (2k - 1)` la baseline monotone ma nhieu paper constrained sau nay noi tiep hoac so sanh.

## Extraction To Syntheses

- `syntheses/k-submodular.md` nen xem day la core paper ngay sau Ward-Zivny.
- Nen dung paper nay lam moc tham chieu cho ca ba nhanh:
  - monotone unconstrained;
  - hardness;
  - derandomization / online / matroid extensions.