# Hirai, Iwamasa 2016 - On k-Submodular Relaxation

## One-paragraph Summary

Day la paper nen tang cho "khi nao mot bai toan multilabel co the duoc relax thanh `k`-submodular". Dong gop trung tam la mot characterization rat sach: `f` co `k`-submodular relaxation khi va chi khi `dom f` dong duoi toan tu ba ngoi `theta` (dual discriminator). Tu characterization do, paper thiet ke mot algorithm `O((kn)^2)` de xay relaxation, kem hai tinh chat rat gia tri cho ung dung: neu input nguyen thi relaxation thu duoc la half-integral; neu input nhi phan (`n = 2`) thi relaxation la maximal duy nhat. Paper nay bien `k`-submodular relaxation thanh mot cong cu co the kiem tra / tinh toan duoc thay vi chi la mot y tuong truu tuong.

## Setup

- Input: `f : [k]^n -> R union {+infty}`.
- Muc tieu: tim `g : [0, k]^n -> R union {+infty}` sao cho:
  - `g` la `k`-submodular;
  - `g(x) = f(x)` voi moi `x in [k]^n`.
- Relaxation phuc vu VCSP, FPT, va partial optimality qua persistency.

## Main Results

1. Theorem 1:
   `f` admit relaxation iff `theta(x, y, z) in dom f` cho moi `x, y, z in dom f`, voi
   `theta(a,b,c) = a` neu `a = b`, con lai bang `c`.
2. Theorem 2:
   co algorithm `O((kn)^2)` quyet dinh ton tai relaxation va xay relaxation neu co.
3. Property 1 cua Theorem 2:
   input integer-valued cho ra relaxation half-integral.
4. Property 2 cua Theorem 2:
   neu `n = 2` thi relaxation tao ra la maximal duy nhat trong tat ca cac relaxation.
5. Theorem 4:
   persistency cho minimizer cua relaxation: label khac `0` trong nghiem toi uu cua `g` co the giu nguyen trong mot nghiem toi uu cua `f`.

## Core Algorithmic Idea

- Xem cac bat dang thuc `k`-submodular nhu mot he linear inequalities tren gia tri `g(x)` cho cac diem moi co chua so `0`.
- Thu tu them cac diem co nhieu so `0` dan, va voi moi diem moi `z`, dinh nghia `g(z)` tu cac cap `(x, y)` sao cho `z = x sqcap y`.
- Neu gap truong hop can co `x sqcup y` nam ngoai closure can thiet, algorithm tra ngay "khong ton tai relaxation".
- Neu di het, ta thu duoc mot ham `g` thoa tat ca inequalities.

## Proof / Analysis Strategy

- Phan structural:
  closure duoi `theta` chinh la dieu kien domain can va du cho viec ton tai relaxation.
- Phan algorithmic:
  paper thuc hien Fourier-Motzkin elimination tren he inequalities `k`-submodular, nhung sap thu tu loai bien theo so luong so `0` de elimination tro nen "greedy":
  cac inequalities co he so am cua bien hien tai da bi loai o cac buoc truoc, nen khong phat sinh no combinatorial.
- Half-integrality den tu cong thuc cap nhat moi diem la trung binh `1/2 (g(x) + g(y))` hoac hieu cua ba gia tri da biet.
- Binary maximality den tu viec construction luon cho gia tri lon nhat co the ma van giu `k`-submodularity.

## Applications Emphasized In The Paper

- VCSP:
  neu moi summand co relaxation, toan instance co the relax sang `k`-submodular VCSP, roi giai bang tractability da biet.
- FPT:
  half-integral relaxation va persistency giup co parameter `d` nho hon cho branching.
- Maximization:
  neu co nonnegative relaxation, co the ap dung `1 / 2`-approximation `k`-submodular tren relaxation de lay approximate solution cho bai toan goc.

## Key Techniques

- dual discriminator `theta`
- closure operators `C_theta`, `C_sqcap`, `C_sqcap,sqcup`
- greedy Fourier-Motzkin elimination
- persistency
- half-integral relaxation
- maximal binary relaxation

## Delicate Points / Caveats

- Paper giai quyet bai toan "ton tai va xay relaxation", khong giai quyet oracle-model minimization cho moi `k`-submodular function.
- Mot phat bieu informal truoc do rang "ham nao cung co relaxation bang cach gan hang so cho cac diem co `0`" la sai; paper neu ro phan vi du phan bien.
- Phan ung dung maximization can nonnegative relaxations, ma paper chi ra huong do la promising chua dong hoan toan.

## Extraction To Concepts

- Nen tao `concepts/k-submodular-relaxation.md` tu paper nay.
- `concepts/k-submodularity.md` nen bo sung:
  - domain-closure viewpoint;
  - half-integrality / persistency.

## Extraction To Syntheses

- `syntheses/k-submodular.md` nen them mot nhanh structural ro:
  `Gridchyn-Kolmogorov -> Hirai-Iwamasa -> Hirai-Oki`.