# Anonymous 2026 - A General Framework for Dynamic Consistent Submodular Maximization

## One-paragraph Summary

Day la paper day notion `consistent submodular maximization` tu insertion-only sang fully dynamic setting co ca insertions lan deletions. Muc tieu khong chi la approximation, ma con la so thay doi giua hai loi giai lien tiep. Paper dua ra mot framework randomized chung dua tren cac "transition windows" va nhieu muc deletion-robustness, roi instantiate no cho hai bai toan: cardinality constraints va matroid constraints. Ket qua la cardinality dat `1/2 - O(epsilon)` voi `O(1/epsilon^2)` consistency, con matroid hang `k` dat `1/4 - O(epsilon)` voi `O(log k / epsilon^2)` consistency. Y tuong trung tam la thay vi doi nghiem ngay lap tuc sau moi update, thuat toan tinh mot nghiem robust moi tai cac moc schedule ngau nhien, sau do chuyen dan tu nghiem cu sang nghiem moi trong mot cua so transition ngan, nhờ vay giu duoc symmetric difference moi buoc o muc sublinear.

## Classification Rationale

Paper thuoc `submodular` vi no lam viec voi monotone submodular maximization tren set systems, nhung diem moi chinh nam o dynamic consistency. No giao thoa manh voi deletion robustness, fully dynamic algorithms, matroid optimization, va stable optimization.

## Setup

- Domain / model: monotone submodular `f : 2^X -> R`.
- Dynamic environment: fully dynamic stream voi insertions va deletions duoi oblivious adversary.
- Feasibility constraints:
  - cardinality `|S| <= k`;
  - matroid constraint rank `k`.
- Approximation notion: randomized approximation in expectation voi `E[f(ALG_t)] >= alpha f(OPT_t)`.
- Consistency notion: `|ALG_t triangle ALG_{t-1}| <= C` moi thoi diem; paper do bang symmetric difference, tu nhien hon trong presence cua deletions.

## Main Results

1. General framework:
   - dung scheduling routine `Random-Scheduling`,
   - mot robust submodular routine `AR`,
   - mot non-robust routine `AN`,
   - va co che transition dan tu nghiem cu sang nghiem moi trong `epsilon' d_i` buoc.
2. Matroid instantiation:
   - `Consistent-Matroid` dat `(1/4 - 7 epsilon)` approximation;
   - consistency `O(log k / epsilon^2)`.
3. Cardinality instantiation:
   - `Consistent-Cardinality` dat `(1/2 - 3 epsilon)` approximation;
   - consistency `O(1/epsilon^2)`.
4. Ve mat y tuong, paper la extension fully dynamic dau tien cua consistency line, truoc do moi co insertion-only cardinality results cua Dutting et al. 2024/2025.

## Core Algorithmic Idea

Framework co ba lop.

Lop 1 la `Random-Scheduling`. Cho hai muc robustness `d0` va `d_ell`, routine tao ra cac level `d_i`, moi level co cac transition times va transition windows rieng. Sau do tat ca duoc random cyclic shift. Cac tinh chat quan trong:

- transition windows khong overlap;
- moi non-transition time `t` co mot transition gan nhat trong khoang `d_i` truoc do cho tung level;
- chi mot `epsilon` fraction thoi gian nam trong transition windows.

Lop 2 la `AR`, robust routine. Tai transition time cua level `i`, routine nay nhan mot nghiem feasible ban dau, mot candidate set, va deletion robustness `d_i`, roi tinh mot nghiem tam `I_t` co kha nang chiu duoc toi da `d_i` deletions trong khoang tiep theo.

Lop 3 la `AN`, non-robust routine. Giua hai transition windows, no chi can cap nhat nghiem nhanh hon tu candidate set hien co.

Tai mot transition time, framework khong nhay truc tiep tu `ALG_old` sang `I_t`, vi lam vay co the pha consistency. Thay vao do, no chia phan khac nhau giua hai nghiem thanh cac chunk, va moi buoc chi chen / loai mot chunk nho. Day la ly do consistency cuoi cung tieu thu phu thuoc vao kich thuoc transition window.

## Proof / Analysis Strategy

- Buoc 1: phan tich scheduling. Lemma 3.2 dam bao transition windows khong overlap, bao phu du de moi time step "gan" mot robust recomputation, va tong mat thoi gian cho transitions chi la `epsilon` fraction.
- Buoc 2: chot abstract guarantee tu framework:
  - tai non-transition times, nghiem hien tai phai gan voi mot nghiem tam duoc robust routine tinh ra gan day;
  - tai transition times, mat mot `epsilon` fraction nhung van kiem soat duoc bang averaging.
- Buoc 3: matroid case.
  - robust routine `Robust-Swap` ket hop deletion-robust sampling cua Zhang et al. voi `Swap` cua Chakrabarti-Kale;
  - sample element theo xac suat ti le nghich voi marginal contribution, roi swap vao neu no du lon so voi phan tu thay the re nhat;
  - dung he weight assignment de phan tich robusness cua superset cac phan tu da tung duoc add.
- Buoc 4: cardinality case.
  - chi can mot muc robustness `d = epsilon^2 k`;
  - robust routine `Robust-Greedy` lap `k - 2d/epsilon` vong, moi vong loc ra `d/epsilon` phan tu marginal lon nhat, roi sample mot phan tu theo xac suat ti le nghich voi marginal;
  - non-robust routine thuc chat rat don gian, vi trong cardinality thi giua transitions co the them dan candidate elements vao solution.
- Buoc 5: cardinality analysis dung threshold lemma.
  - Neu `|I_t'|` da gan `k`, thi threshold `theta` khong cho optimum co tong marginal vuot qua current solution qua nhieu.
  - Neu `|I_t'|` con nho hon `k(1-2epsilon)`, thi tat ca phan tu con lai deu co zero marginal vao tam solution, nen current solution da absorb het gia tri con lai.

## Key Techniques

- multi-level random scheduling over robustness scales
- transition windows for consistency-preserving migration
- robust versus non-robust routine separation
- deletion-robust submodular maximization as a subroutine
- inverse-marginal sampling
- hybrid greedy-threshold analysis for cardinality

## Key Lemmas Or Structural Claims

- Lemma 3.2: bat ky realization nao cua `Random-Scheduling` cung cho non-overlapping transition windows, bounded recency to the last transition time at every robustness level, va chi ton `epsilon` fraction thoi gian trong transitions.
- Matroid side:
  - robust sampled superset `U` van giu duoc mot phan lon tong weight sau deletions;
  - weight cua cac phan tu bi swap-out duoc upper-bound bang weight cua nghiem tam;
  - tu do non-transition solution van giu `1/4 - O(epsilon)` cua optimum.
- Cardinality side:
  - ton tai threshold `theta` sao cho hoac nghiem tam da rat day va moi phan tu con lai co marginal `<= theta`, hoac tat ca phan tu chua xu ly deu zero-marginal;
  - suy ra `f(OPT_t) <= (2 + O(epsilon)) f(ALG_t)` o non-transition times, va averaging tren transition times cho ra `1/2 - 3 epsilon`.

## Delicate Points / Caveats

- Paper anonymous nen metadata venue / tac gia chua final.
- Approximation la in expectation, nhung consistency la worst-case / realization-wise.
- Framework nhan manh consistency, khong toi uu amortized running time nhu fully dynamic literature co dien.
- Matroid result co khoang cach ky thuat ro so voi cardinality: framework giong nhau, nhung robust routine va proof phuc tap hon nhieu.
- Paper chi xu ly monotone objectives; conclusion nêu ro non-monotone va knapsack la huong mo.

## Extraction To Concepts

- Dinh nghia / notation nen dua vao `concepts/`:
  - fully dynamic consistency measured by symmetric difference;
  - transition windows / robustness levels as a general design pattern.
- Lemma co the tai su dung:
  - random scheduling to spread solution migration over time;
  - inverse-marginal robust sampling.
- Technique lap lai:
  - robust coreset + gradual migration;
  - hybrid greedy-threshold proof for dynamic cardinality consistency.
- Quan he voi nhom khac:
  - noi consistency line cua Dutting et al. 2024 voi deletion-robust submodular maximization;
  - noi them sang fully dynamic matroid submodular maximization.

## Extraction To Syntheses

- Cap nhat [submodular.md](C:\Users\Admin\Documents\GitHub\SubResearch\syntheses\submodular.md) de them nhanh fully dynamic consistency line.
- Cap nhat concept [consistent-submodular-maximization.md](C:\Users\Admin\Documents\GitHub\SubResearch\concepts\consistent-submodular-maximization.md) de them symmetric-difference view va fully dynamic extension.
- Khong can cap nhat [k-submodular.md](C:\Users\Admin\Documents\GitHub\SubResearch\syntheses\k-submodular.md).
- Khong can cap nhat [dr-submodular.md](C:\Users\Admin\Documents\GitHub\SubResearch\syntheses\dr-submodular.md).

## Weaknesses / Limits

- can randomization; paper khong dua deterministic fully dynamic counterpart co quality tuong tu
- matroid ratio `1/4 - O(epsilon)` van thap hon cardinality va con cach xa insertion-only consistency line
- framework can cac robust routines problem-specific, nen khong phai chi can "plug-and-play" mot cach hoan toan den cap do black box

## Research Ideas Triggered

- Co the dat constant consistency cho fully dynamic matroid while van giu approximation hang so khong?
- Co the mo rong framework sang non-monotone objectives, knapsack, hay p-matchoid constraints khong?
- Co the cai thien cardinality tu `1/2 - O(epsilon)` len muc gan insertion-only best-known while van giu fully dynamic consistency sublinear khong?