# Submodular Function Minimization

## Related Groups

- submodular

## Type

- relation
- technique

## Statement

Submodular function minimization (SFM) la bai toan tim tap `S` toi thieu hoa `f(S)` khi `f` duoc truy cap qua value oracle. Day la mot nhanh rat khac voi maximization: ve mat ly thuyet co the giai chinh xac trong thoi gian da thuc, va lien he sau sac voi discrete convexity.

## Intuition

Maximization thuong di theo huong approximation; minimization thuong di theo huong exact algorithms va structural theory. Vi vay trong repo can tach ro "maximization lineage" va "SFM lineage".

## Equivalent Views

- oracle minimization problem
- discrete-convex / Lovasz-extension viewpoint

## Standard Examples

- Iwata survey
- McCormick survey
- Schrijver strongly polynomial algorithm

## Related Results

- SFM co combinatorial strongly polynomial algorithms
- Lovasz extension giup noi SFM voi convex analysis

## Where It Is Used

- `2007-iwata-submodular-function-minimization-survey`
- `2007-mccormick-on-submodular-function-minimization`
- `2000-schrijver-combinatorial-submodular-minimization`