# Consistent Submodular Maximization

## Related Groups

- submodular

## Type

- definition
- algorithmic-theme

## Statement

Trong insertion-only setting, ta duy tri mot loi giai `S_t` sau moi insertion. Ngoai approximation thong thuong, ta them mot rang buoc consistency: thuat toan la `C`-consistent neu `|S_t \\ S_{t-1}| <= C` cho moi `t >= 2`.

Trong fully dynamic setting, notion tu nhien hon la symmetric-difference consistency:

- `|ALG_t triangle ALG_{t-1}| <= C` cho moi `t`,

vi khi co deletions, viec chi dem so phan tu moi them vao khong con du de mo ta muc thay doi cua loi giai.

Muc tieu la dat loi giai vua co gia tri lon so voi `OPT_t`, vua thay doi it qua thoi gian.

## Intuition

Nhieu ung dung can summary / recommendation / seed set thay doi mem va du doan duoc, khong phai moi insertion lai "quay xe" toan bo. Consistency vi vay tro thanh mot objective rieng, khong the coi chi la he qua phu cua query efficiency hay low update time.

## Equivalent Views

- stability of the maintained solution
- dynamic insertion model voi objective "smoothness" cua loi giai
- fully dynamic optimization voi rang buoc on dinh worst-case moi buoc

## Standard Examples

- `1`-consistent benchmark-set algorithm
- local-optimum-chasing voi `O~(1/epsilon)` consistency
- fully dynamic cardinality algorithm voi `O(1/epsilon^2)` consistency
- fully dynamic matroid algorithm voi `O(log k / epsilon^2)` consistency

## Related Results

- Dutting et al. 2024 mo huong nay cho monotone submodular maximization duoi cardinality
- cung paper do cho lower bound: voi deterministic algorithms va constant consistency, khong the vuot qua `2 - epsilon`
- notion nay co lien he voi fully dynamic optimization, nhung khong dong nhat voi amortized update time
- anonymous ICML 2026 framework mo notion nay sang fully dynamic insert-delete setting, do bang symmetric difference, va ket hop consistency voi deletion-robust subroutines

## Where It Is Used

- `2024-dutting-et-al-consistent-submodular-maximization`
- `2026-anonymous-general-framework-dynamic-consistent-submodular-maximization`