# K-Submodular Min-Max Theorem

## Related Groups

- k-submodular
- submodular

## Type

- theorem
- polyhedral-view

## Statement

Voi mot ham `k`-submodular `f : T^n -> R` thoa `f(0) = 0`, Huber va Kolmogorov cho thay:

`min_T f(T) = max_{x in U(f)} -||x||_1`.

Tap `U(f)` gom cac unified vectors nam duoi `f`: moi coordinate chon mot leaf "duong", dat gia tri `+x_i` tren leaf do, `-x_i` tren moi leaf con lai, va bat dang thuc `(x, L)(T) <= f(T)` phai dung voi moi labeling `T`.

Neu `f` la integer-valued thi co the chon mot chung chi toi uu nguyen.

## Intuition

Day la phien ban `k`-submodular cua viewpoint Edmonds / bisubmodular: gia tri cuc tieu cua ham bang dung luong "negative mass" lon nhat ma mot chung chi polyhedral hop le co the dat duoc. Diem khac kho la voi `k >= 3`, khong phai moi vector trong polyhedron lon hon deu co hinh dang unified, va chinh tap unified moi la doi tuong dung cho Min-Max theorem.

## Equivalent Views

- generalization cua submodular Min-Max theorem
- generalization cua bisubmodular Min-Max theorem
- exact minimization certificate thong qua unified vectors trong `k`-submodular polyhedron `P(f)`

## Standard Examples

- `k = 1`: quay ve Min-Max theorem cua Edmonds cho submodular functions
- `k = 2`: quay ve bisubmodular Min-Max theorem
- `k >= 3`: cho chung chi minimization chinh xac, nhung chua du de suy ra polynomial-time oracle minimization

## Related Results

- Huber-Kolmogorov 2013 chung minh Min-Max theorem, dinh nghia `P(f)`, va nhan manh tro ngai "good characterization"
- Fujishige-Tanigawa 2013 dua ra mot theorem yeu hon tren polyhedron `PF_T(f)` voi norm `||.||_{1,infty}`
- rank functions cua `k`-matroids / multimatroids cho mot nguon vi du tu nhien cho `k`-submodularity

## Where It Is Used

- `2013-huber-kolmogorov-towards-minimizing-k-submodular-functions`
- cac paper minimization / polyhedral k-submodular ve sau