# Oshima 2017 - Derandomization for k-submodular maximization

## One-paragraph Summary

Paper nay dong mot lo hong ro trong line monotone unconstrained: Iwata-Tanigawa-Yoshida da co ratio `k / (2k - 1)` nhung van randomized; Oshima chi ra co the derandomize hoan toan ma khong mat ratio. Y tuong la khong chon ngau nhien mot nhan cho moi phan tu nua, ma duy tri mot phan phoi huu han tren cac partial assignments. O moi buoc, giai mot LP de cap nhat phan phoi sao cho one-step inequality cua proof randomized van dung trong ky vong; cuoi cung chi can lay assignment tot nhat trong support.

## Setup

- Input: monotone nonnegative `k`-submodular function `f : {0, ..., k}^V -> R_+`.
- Muc tieu: deterministic approximation matching randomized ratio `k / (2k - 1)`.

## Main Results

1. Theorem 3:
   Algorithm 3 tra ve nghiem `z` voi
   `f(z) >= (k / (2k - 1)) f(o)`.
2. Running time polynomial:
   paper giu support distribution polynomial bang cach chon extreme-point solution cua LP cap nhat.

## Core Algorithmic Idea

- Thay mot nghiem partial `s`, paper duy tri mot phan phoi `D_j` tren nhieu nghiem partial.
- Tai buoc xu ly phan tu `e(j)`:
  - voi moi support point `s`, tinh marginal gains `y_i(s)`;
  - tim cac he so `p_{i,s}` thoa mot he linear constraints bieu dien chinh one-step inequality ma proof randomized can;
  - sinh phan phoi moi `D_j` bang cach "tach" moi `s` thanh cac assignment moi khi gan `e(j)` vao nhan `i`.
- Cuoi cung, do `E_{s ~ D_n}[f(s)]` da dat ratio mong muon, assignment tot nhat trong support cung dat ratio do.

## Proof / Analysis Strategy

- Proof van dung lemma meta cua Iwata-Tanigawa-Yoshida:
  neu moi buoc expected loss cua optimum duoc chan boi `(1 - 1 / k)` lan expected gain, thi tong the ratio la `k / (2k - 1)`.
- LP constraints trong paper duoc chon de dam bao bat dang thuc nay cho moi label optimum co the.
- Chon extreme point quan trong vi no giu support cua distribution tang co kiem soat, tranh no combinatorial.
- Sau `n` buoc:
  `E[f(s)] >= (k / (2k - 1)) f(o)`,
  nen phan tu tot nhat trong support khong the thap hon ky vong do.

## Key Techniques

- derandomization qua distributions tren partial assignments
- LP encoding cua one-step approximation proof
- extreme-point support compression
- monotone randomized-greedy transfer

## Delicate Points / Caveats

- Paper chi xu ly monotone unconstrained case.
- Derandomization o day khong cho ratio tot hon; no quan trong vi loai bo randomness va cho thay proof randomized co the duoc "linearized".
- Distribution-support method co the nang hon ve mat thuc te so voi randomized version, du van polynomial.

## Extraction To Concepts

- `concepts/k-submodularity.md` nen bo sung rang monotone baseline `k / (2k - 1)` co ban deterministic.

## Extraction To Syntheses

- `syntheses/k-submodular.md` nen them paper nay vao line:
  `Iwata-Tanigawa-Yoshida -> Oshima derandomization -> Soma online`.