# k-Submodular Relaxation

## Related Groups

- k-submodular
- mixed

## Type

- definition
- relaxation
- persistency

## Statement

Cho mot ham multilabel `f : [k]^n -> R union {+infty}`, mot `k`-submodular relaxation la mot ham
`g : [0, k]^n -> R union {+infty}` sao cho:

- `g` la `k`-submodular;
- `g(x) = f(x)` voi moi `x in [k]^n`.

Gia tri `0` dong vai tro "khong gan nhan / undecided". Vi the relaxation nay khong chi la mot lower-dimensional extension ky thuat; no la cong cu de rut ra partial assignments co the giu nguyen trong mot nghiem toi uu cua bai toan goc.

## Intuition

Trong nhieu bai toan multilabel, tim optimum goc la kho. `k`-submodular relaxation mo rong khong gian nghiem bang cach them nhan `0`, de bai toan tro nen co cau truc `sqcap / sqcup` tot hon. Neu minimizer cua relaxation dat mot bien vao nhan khac `0`, label do thuong mang y nghia "persistently optimal".

## Equivalent Views

- multilabel analogue cua roof-duality / bisubmodular relaxation
- partial-optimality certificate cho bai toan discrete
- cau noi giua VCSP / Potts energies va `k`-submodular minimization

## Standard Examples

- Potts energy relaxations trong computer vision
- valued CSP instances ma moi summand nho co the relax duoc
- binary instances ma relaxation maximal co the tinh combinatorially

## Related Results

- Gridchyn, Kolmogorov 2013:
  dua ra natural `k`-submodular relaxations cho Potts energies va nhan manh persistency; dong thoi chi ra Kovtun preprocessing co the manh hon relaxation tu nhien.
- Hirai, Iwamasa 2016:
  cho characterization day du:
  `f` co relaxation iff `dom f` dong duoi dual-discriminator `theta`;
  kem algorithm `O((kn)^2)` de tim relaxation hoac chung minh khong ton tai.
- Cung paper Hirai-Iwamasa:
  neu input nguyen thi relaxation thu duoc la half-integral; neu `n = 2` thi relaxation la maximal duy nhat.
- Persistency:
  neu `y*` la minimizer cua relaxation `g`, thi ton tai minimizer `x*` cua bai toan goc sao cho moi toa do `y*_i != 0` deu duoc giu lai trong `x*`.
- Hirai, Oki 2017:
  tap minimizers cua mot `k`-submodular function co the duoc ma hoa bang elementary PIP, nen relaxation khong chi giup tim mot partial optimum ma con giup mo ta cau truc cua tat ca partial optima.

## What To Be Careful About

- Khong phai ham nao cung co `k`-submodular relaxation. Dieu kien ton tai la structural, khong phai "gan hang so cho cac diem co `0`" mot cach tu dong.
- Co relaxation roi van chua chac la practical, neu chua co minimization oracle hoac subclass tractable.
- Trong Potts case, relaxation tu nhien va Kovtun preprocessing co lien he nhung khong tuong duong; preprocessing co the label nhieu dinh hon.

## Where It Is Used

- `2013-gridchyn-kolmogorov-potts-parametric-maxflow-k-submodular`
- `2016-hirai-iwamasa-k-submodular-relaxation`
- `2017-hirai-oki-pip-representation-k-submodular-minimizers`