# Sakaue 2016 - On maximizing a monotone k-submodular function subject to a matroid constraint

## One-paragraph Summary

Day la paper dau tien trong repo dua `k`-submodular monotone sang rang buoc matroid. Ket qua chinh rat gon: greedy tu nhien, moi buoc chon cap `(e, i)` co marginal lon nhat trong cac phan tu van con co the them vao mot tap doc lap cua matroid, da du de dat `1 / 2`. Vi monotone unconstrained baseline cua Iwata-Tanigawa-Yoshida la asymptotically tight, paper nay cho thay moc `1 / 2` van giu duoc duoi matroid ma khong can continuous-greedy.

## Setup

- Ground set `E`, matroid `(E, F)`.
- Feasible solution `x = (X_1, ..., X_k)` thoa `union_l X_l in F`.
- Objective `f : (k + 1)^E -> R` la monotone `k`-submodular, chuan hoa `f(0) = 0`.

## Main Results

1. Theorem 2:
   greedy algorithm dat `1 / 2`-approximation cho bai toan monotone `k`-submodular duoi matroid.
2. Complexity:
   `O(M |E| (MO + k EO))`, trong do `M` la kich thuoc cua moi basis / maximal optimal support.
3. Lemma 1:
   moi maximal optimal solution deu co support kich thuoc `M`, nen co the doi chieu voi mot basis sequence.

## Core Algorithmic Idea

- Giai phap `s` bat dau rong.
- Lap `M` lan:
  - duy qua moi phan tu `e` co the them vao support ma van giu tinh doc lap cua matroid;
  - voi moi `e`, tim nhan `i` cho marginal `Delta_{e,i} f(s)` lon nhat;
  - chon cap `(e, i)` tot nhat va them vao.
- Khong co randomization hay continuous relaxation; tat ca nam o mot exchange argument thuan combinatorial.

## Proof / Analysis Strategy

- Chon mot optimal solution `o` co support la mot basis.
- Xay day lai `o(0), o(1), ..., o(M)`:
  - `o(0) = o`;
  - moi buoc thay mot phan tu cua support optimum bang phan tu greedy vua chon, nhung van giu duoc basis nho exchange cua matroid.
- Lemma exchange cho phep tim `o(j)` sao cho:
  - support cua `o(j)` van la basis;
  - support cua greedy sau `j` buoc nam ben trong support cua `o(j)`.
- Tu orthant submodularity va monotonicity:
  `gain_greedy(j) >= loss_opt(j)`.
- Cong don qua `j = 1..M`:
  `f(o) - f(s) <= f(s) - f(0) = f(s)`,
  suy ra `f(s) >= f(o) / 2`.

## Key Techniques

- matroid basis exchange
- hybrid optimum sequence
- orthant-submodular marginal comparison
- greedy over feasible element-label pairs

## Delicate Points / Caveats

- Paper chi xu ly monotone case.
- Query complexity con phu thuoc tuyen tinh vao `M` va `|E|`; Niu et al. 2023 sau nay moi cai thien phan "nhanh" bang threshold-decreasing.
- Ratio `1 / 2` dung cho matroid roi, nhung khong tu dong chuyen sang non-monotone hay multiple matroids.

## Extraction To Concepts

- `concepts/k-submodularity.md` nen bo sung ro rang:
  greedy matroid `1 / 2` la combinatorial baseline truoc khi co line threshold nhanh va multilinear extension.

## Extraction To Syntheses

- `syntheses/k-submodular.md` nen them paper nay vao matroid-constrained lineage:
  `Sakaue -> Rafiey-Yoshida (private) -> Niu et al. (fast)`, va so sanh voi Huang-Wang-Zhou continuous line.