# Approximate k-Submodularity

## Related Groups

- k-submodular
- mixed

## Type

- definition
- robustness
- relation

## Statement

Approximate `k`-submodularity nới lỏng cấu trúc `k`-submodular exact bằng một hệ số sai số `eps`. Hai notion chính hiện có trong repo là:

- `eps`-approximately k-submodular (`eps`-AS): bat dang thuc `k`-submodularity chi dung den he so nhan `(1 +- eps)`;
- `eps`-approximately diminishing returns (`eps`-ADR): local diminishing-returns inequalities chi dung den mot he so nhan.

## Intuition

No la cach formal hoa tinh huong objective duoc hoc / sketch / noise / xap xi, nen khong con exact `k`-submodular nhung van gan du de greedy co the hoat dong voi ty le giam mem theo `eps`.

## Equivalent Views

- multiplicative relaxation cua `k`-submodularity
- noisy / learned assignment-domain objective
- exact-proxy model, trong do ton tai mot ham `k`-submodular `f` sao cho `(1 - eps) f <= F <= (1 + eps) f`

## Standard Examples

- sensor placement voi measurement noise
- influence maximization voi uncertainty trong gia tri anh huong
- sketch / learned objective tren assignment domain

## Related Results

- Zheng et al. 2021 la paper canonical hien tai cho notion nay
- `eps`-ADR manh hon `eps`-AS va keo theo `eps`-AS
- voi total-size va individual-size constraints, greedy ratios cho `eps`-ADR dep hon ro so voi `eps`-AS
- neu co mot exact proxy `f`, moi `alpha`-approximation cho `f` chuyen thanh `((1 - eps) / (1 + eps)) alpha`-approximation cho `F`

## Where It Is Used

- `2021-zheng-et-al-maximizing-approximately-k-submodular-functions`