# Submodular Cover

## Related Groups

- submodular
- dr-submodular
- mixed

## Type

- problem-setting
- lineage

## Statement

Submodular cover gom cac bai toan dang "tim nghiem re nhat de utility submodular dat mot muc dich". Thay vi toi da hoa utility voi budget cho truoc, ta dao chieu bai toan: toi thieu hoa cost duoi rang buoc `f(S) >= T`.

## Intuition

Day la nhanh rat tu nhien ben canh maximization. Neu maximization hoi "voi ngan sach B, lay duoc bao nhieu gia tri?", thi cover hoi "de dat muc utility T, can tra gia bao nhieu?". Vi the:

- greedy / thresholding thuong dua tren marginal-per-cost;
- guarantees hay o dang bicriteria;
- streaming va lattice generalizations deu xuat hien rat tu nhien.

## Recurring Techniques

- ratio `marginal gain / cost`
- bicriteria approximation
- threshold schedules va geometric guessing
- special handling cho tiny-cost elements hoac cheap elements
- reductions tu set case sang generalized / lattice case

## Where It Is Used

- `1998-bar-ilan-kortsarz-peleg-generalized-submodular-cover`
- `2013-iyer-bilmes-submodular-cover-knapsack-constraints`
- `2015-soma-yoshida-generalized-submodular-cover-integer-lattice`
- `2023-tran-et-al-streaming-min-cost-submodular-cover`