# Anonymous 2026 - Unconstrained Submodular Maximization in Dynamic Setting

## One-paragraph Summary

Day la paper mo nhanh dynamic unconstrained submodular maximization (USM) vuot qua moc `0.25` trong setting dong. Paper xet ba model: incremental insertions, decremental deletions voi thu tu xoa biet truoc, va fully dynamic updates khi deletion time cua moi phan tu duoc tiet lo luc insertion. Y tuong cot loi la chia tap hien tai thanh mot kho "permanent" kich thuoc lon va mot buffer kich thuoc `sqrt(n)`, roi duy tri hai ung vien: mot nghiem chay tren kho permanent bang mo rong offline algorithm cua Buchbinder et al., va mot nghiem mo rong tu random half-sample cua kho permanent sang buffer. Neu optimum chu yeu nam trong kho permanent thi nghiem thu nhat du; neu optimum co dong gop lon trong buffer thi nghiem thu hai lay lai du gia tri de dat ratio `0.3`. Trong model fully dynamic, paper ket hop kho permanent nay voi mot decremental instance duoc sap xep theo predicted deletion times, dat ratio `0.264`.

## Classification Rationale

Paper thuoc `submodular` vi no lam viec voi unconstrained set-submodular maximization trong oracle model. No giao thoa voi dynamic algorithms, streaming-style buffering, va non-monotone optimization, nhung khong thuoc nhanh cardinality / matroid / knapsack co rang buoc.

## Setup

- Domain / model: unconstrained maximization cua mot ham con `f : 2^V -> R_{>=0}` khong am va co the non-monotone.
- Oracle / access model: value-oracle / set-query model; query complexity duoc tinh theo so lan goi gia tri sau moi update.
- Dynamic models:
  - incremental: chi co insertions;
  - decremental: chi co deletions, va thu tu xoa biet truoc;
  - fully dynamic: co ca insertions lan deletions, va deletion time cua moi phan tu duoc biet ngay khi insert.
- Adversary: oblivious adversary.
- Assumptions:
  - trong phan incremental va decremental, paper viet phan tich voi stream length `n` biet truoc de dat nguong buffer `sqrt(n)`, roi note cach bo gia thiet nay bang threshold doubling;
  - fully dynamic version can biet deletion time / removal order cua moi phan tu.

## Main Results

1. Generalized offline primitive: thu tuc `Extend(S, N)` mo rong random-USM cua Buchbinder et al. sang bai toan "optimal extension", van dung `O(|N|)` queries va thoa inequality kieu
   `f(OPT(S,N)) + f(S) + f(S union N) <= 2 E[f(output)]`.
2. Incremental dynamic USM: co thuat toan dat `E[f(Sol_t)] >= 0.3 f(OPT_t)` voi amortized `O(sqrt(n))` queries per update.
3. Decremental USM voi known-order deletions: mot phien ban "reverse" cua incremental algorithm cung dat `0.3`-approximation va amortized `O(sqrt(n))` queries.
4. Fully dynamic USM voi deletion-time predictions: ket hop increment-only buffer voi decremental instance tren permanent block, dat `0.264`-approximation va amortized `O(sqrt(n))` queries.

## Core Algorithmic Idea

Trong version incremental, tap hien tai `V_t` duoc tach thanh hai khoi:

- `N1`: kho permanent, chi duoc lam moi sau moi dot buffer-day;
- `N2`: buffer cua cac phan tu moi, co kich thuoc toi da `sqrt(n)`.

Thuat toan giu ba doi tuong:

- `Sol1 = Extend(emptyset, N1)`, dong vai tro nghiem "co so" cho kho permanent;
- `S1 = N1(1/2)`, random half-sample cua `N1`;
- `Sol2 = Extend(S1, N2)`, nghiem mo rong tu random half-sample sang buffer.

Luc nao cung output `arg max{f(Sol1), f(Sol2)}`. Truc giac:

- neu optimum hien tai an chu yeu trong `N1`, thi `Sol1` gan offline `1/2` approximation tren kho do;
- neu optimum lay duoc nhieu gia tri tu `N2`, thi `Sol2` huong den bai toan "start from a random half of `N1`, then extend by `N2`", va phan gain tu `N2` bu lai du de vuot `0.25`.

Version decremental dao nguoc phan hoach tren:

- `M2` la phan chua den luot xoa;
- `M1` la block sap bi xoa trong `sqrt(n)` buoc ke tiep.

Paper sample random half `S2` cua `M2`, tinh `Sol2' = Extend(emptyset, M2)` va `Sol1' = Extend(S2, M1)`, roi tra ve nghiem tot hon.

Version fully dynamic giu y tuong buffer `N2` nhu incremental, nhung moi khi buffer flush vao `N1` thi sap `N1` theo deletion time va khoi tao mot instance decremental tren `N1`. Khi mot phan tu trong `N1` bi xoa, instance decremental xu ly no; khi mot phan tu trong `N2` bi xoa, chi can xoa khoi buffer. `Sol2` van duoc tinh bang `Extend(S1, N2)` sau moi update.

## Proof / Analysis Strategy

- Buoc 1: chung minh primitive `Extend(S, N)` ke thua dung phan tich cua random-USM sau khi dich ham thanh `g(A) = f(S union A)`.
- Buoc 2: incremental case. Viet `OPT = (OPT cap N1) union (OPT cap N2)`.
  - Neu `f(OPT cap N1)` lon, thi `Sol1` duoc lower-bound bang `1/2` cua optimum restricted to `N1`, suy ra `>= 3/10 f(OPT)`.
  - Neu `f(OPT cap N1)` nho, thi do submodularity phan optimum trong `N2` phai lon. Khi do dung random-half lemma kieu Feige-Mirrokni-Vondrak tren `N1(1/2)` va inequality cua `Extend` de lower-bound `Sol2`.
- Buoc 3: ghep hai case thanh Lemma 19, chi ra `max(E[f(Sol1)], E[f(Sol2)]) >= 3/10 f(OPT)`.
- Buoc 4: phan tich query complexity. `Sol2` luon chi can `O(|N2|) = O(sqrt(n))` queries. `Sol1` ton `O(n)` moi lan rebuild, nhung rebuild chi xay ra sau moi `sqrt(n)` insertions, nen amortized la `O(sqrt(n))`.
- Buoc 5: decremental case. Lap lai cung khung proof voi vai tro cua `M1`, `M2`, va random half-sample cua `M2`; y tuong la phan "chua xoa" dong vai tro permanent-side trong reverse time.
- Buoc 6: fully dynamic case. Tach optimum theo `N1` va `N2` nhu incremental, nhung `Sol1` khong con la `1/2`-approximation ma chi la `3/10`-approximation cua decremental subproblem tren `N1`. Vi vay khi ghep hai case, constant giam tu `3/10` xuong `9/34 = 0.264...`.

## Key Techniques

- generalized offline extension primitive based on random-USM
- `sqrt(n)`-buffer decomposition to trade off rebuild cost and update cost
- random half-sampling of the permanent block
- two-solution strategy: one tracks the old block, one exploits the recent buffer
- reverse-time decremental analogue
- fully dynamic reduction using predicted deletion times

## Key Lemmas Or Structural Claims

- `Extend(S, N)` satisfies the same `1/2`-style inequality as offline random-USM after shifting the baseline to `S`.
- If the optimum contribution inside the permanent block is already a constant fraction of total optimum, then the permanent-side solution is enough.
- If the permanent-side contribution is small, then submodularity forces significant value to remain in the buffer, and the random-half extension solution captures a constant fraction of it.
- In the fully dynamic reduction, the decremental algorithm on `N1` provides the `Sol1` side and changes only the constant in the final case split.

## Delicate Points / Caveats

- Paper la anonymous reviewer copy; metadata tac gia / venue chua on dinh.
- Fully dynamic result khong dung trong model deletions tuy y; no can deletion times duoc reveal luc insertion.
- Ratios `0.3` va `0.264` la theo convention `E[f(S_t)] >= c f(OPT_t)`, tuc ratio "theo huong lon hon thi tot hon", khac voi mot so paper consistency viet theo approximation factor `c >= 1`.
- Kich thuoc buffer duoc chon theo `sqrt(n)`, vi vay phan tich query complexity duoc gắn chat voi stream length hoac mot co che threshold-doubling.
- Paper khong dat tight `1/2`; no nham vao barrier "vuot 0.25 voi sublinear update time" trong USM dong.

## Extraction To Concepts

- Dinh nghia / notation nen dua vao `concepts/`:
  - khong can concept rieng chi cho paper nay, vi ky thuat buffer `N1/N2` va reverse decremental analogue hien van rat paper-specific.
- Lemma co the tai su dung:
  - generalized `Extend(S, N)` view cua random-USM la mot reusable proof trick cho dynamic decompositions.
- Technique lap lai:
  - random-half permanent core + extension over a fresh buffer.
- Quan he voi nhom khac:
  - noi tu offline random-USM cua Buchbinder et al. sang dynamic USM;
  - gan voi dynamic submodular maximization line, nhung xu ly unconstrained non-monotone setting.

## Extraction To Syntheses

- Cap nhat [submodular.md](C:\Users\Admin\Documents\GitHub\SubResearch\syntheses\submodular.md) de them nhanh dynamic unconstrained USM.
- 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

- fully dynamic result can deletion-time predictions, nen manh hon nhung cung hep hon model fully dynamic tong quat
- query/update guarantee la sublinear nhung approximation van kha xa moc offline `1/2`
- ky thuat decremental va fully dynamic duoc dua vao Appendix va ve co ban la bien the cua cung mot phan hoach hai-khoi

## Research Ideas Triggered

- Co the bo gia thiet reveal deletion time ma van giu ratio > `0.25` voi sublinear update time hay khong?
- Co the cai thien moc `0.3` incremental/decremental bang mot phien ban manh hon cua random-USM extension hay bang coreset robust hon khong?
- Co the dua y tuong two-block `permanent + buffer` sang constrained non-monotone settings nhu matroid hay knapsack hay khong?