# Submodularity

## Related Groups

- submodular
- k-submodular
- dr-submodular

## Type

- definition
- relation

## Statement

Voi set function `f : 2^V -> R`, tinh submodular duoc phat bieu boi bat dang thuc:

`f(S) + f(T) >= f(S union T) + f(S intersection T)` voi moi `S, T subseteq V`.

Trong nhieu setting, day la discrete analogue cua convexity va cung co the duoc nhin qua diminishing returns.

## Intuition

Them mot phan tu vao mot tap nho thuong giup nhieu hon them cung phan tu do vao mot tap da lon. Truc giac nay la hat nhan cua rat nhieu approximation guarantees cho greedy va cung la diem neo de mo rong sang bisubmodular, k-submodular, va DR-submodular settings.

## Equivalent Views

- lattice inequality view
- diminishing-returns view trong nhieu class function quan trong

## Standard Examples

- matroid rank functions
- cut functions
- coverage functions

## Related Results

- Edmonds dat viewpoint rank / polymatroid
- Nemhauser-Wolsey-Fisher dat greedy approximation line kinh dien
- SFM literature dung Lovasz-extension / convexity analogy de giai thich minimization

## Where It Is Used

- `1970-edmonds-submodular-functions-matroids-polyhedra`
- `1978-nemhauser-wolsey-fisher-maximizing-submodular-set-functions`
- cum survey / minimization papers