# Greedy Cardinality Approximation

## Related Groups

- submodular
- k-submodular

## Type

- lemma
- technique

## Statement

Trong monotone submodular maximization duoi cardinality constraint, greedy bang cach chon phan tu co marginal gain lon nhat moi buoc dat bound kinh dien tien ve `1 - 1/e`.

## Intuition

Moi buoc greedy "an" mot phan hang so cua khoang cach den optimum. Day la motif co ban cua phan tich submodular maximization va rat nen tang cho nhieu bien the sau nay nhu streaming hay randomized greedy.

## Equivalent Views

- multiplicative shrinkage of the residual gap
- marginal-gain charging argument

## Standard Examples

- Nemhauser-Wolsey-Fisher classical cardinality setting
- so sanh lich su voi streaming threshold methods

## Related Results

- `1 - 1/e` la moc reference trung tam trong submodular maximization
- greedy lineage mo rong sang batched, streaming, va random-order variants

## Where It Is Used

- `1978-nemhauser-wolsey-fisher-maximizing-submodular-set-functions`
- `2014-badanidiyuru-et-al-streaming-submodular-maximization`
- `2019-liu-et-al-greedy-strategies-survey`