# Chen et al. 2024 - Discretely Beyond 1/e: Guided Combinatorial Algorithms for Submodular Maximization

## One-paragraph Summary

Day la paper moc cho non-monotone submodular maximization duoi size va matroid constraints: lan dau tien co combinatorial algorithms vuot moc `1 / e` ma khong can multilinear extension hay gradient estimates. Paper dat `0.385 - epsilon` cho size constraints va `0.305 - epsilon` cho matroid constraints trong `O(kn / epsilon)` queries, dong thoi dua ra cac phien ban deterministic cung ratios nay. Quan trong hon, paper chi ra mot spine ro rang: tim mot local optimum "guidance set" re, roi dung no de huong dan random greedy / interpolated greedy. Tu do paper con dat mot deterministic nearly-linear algorithm ratio `0.377`.

## Classification Rationale

Paper thuoc `submodular` va nam thang vao nhanh non-monotone constrained maximization. Ve lineage, no ngoi giua:

- RANDOM GREEDY va INTERPOLATED GREEDY cho combinatorial `1 / e`;
- Buchbinder-Feldman 0.385 continuous line;
- cac cong trinh practical / parallel sau do trong inbox cung cluster nay.

No la diem neo ly thuyet, trong khi Tukan et al. 2024 la diem neo practical cho size constraint va Chen et al. 2025 day tiep sang sublinear-adaptivity.

## Setup

- Objective: non-negative, not necessarily monotone submodular maximization.
- Constraints: size constraint va general matroid constraint.
- Access model: chi query set-function oracle, khong query multilinear extension.
- Targets: combinatorial, deterministic, va nearly-linear-time algorithms.

## Main Results

1. Randomized combinatorial algorithm dat `0.385 - epsilon` cho size constraint.
2. Randomized combinatorial algorithm dat `0.305 - epsilon` cho general matroid constraint.
3. Deterministic phien ban dat cung ratios voi query complexity cung bac `O(kn / epsilon)`.
4. Deterministic nearly-linear algorithm dat `0.377` trong query complexity gan `O_epsilon(n log k)`.

## Core Algorithmic Idea

Paper tach thanh hai khoi:

- `FAST LS`: mot local search nhanh tao ra mot set `Z` gia tri khong qua lon nhung co tinh chat guidance tot doi voi optimum.
- `GUIDED RG` / `GUIDED INTERPOLATED GREEDY`: giai doan greedy duoc huong dan boi `Z`, tuc la ban dau cam / han che di vao `Z` de buoc recurrences cua random greedy tro nen co loi hon.

Ve nearly-linear version, paper khong thuc su chay local search day du nua, ma rut guidance information tu mot lan chay unguided interpolated greedy, roi dung no de dat ratio `0.377`.

## Proof / Analysis Strategy

Spine proof xoay quanh khai niem `guidance set`.

- FAST LS tra ve `Z` sao cho neu `f(Z)` chua lon thi ca `f(OPT union Z)` va `f(OPT inter Z)` deu bi khong che boi `f(Z)`.
- Tu do, khi GUIDED RG ban dau tranh cac phan tu trong `Z`, recurrences kinh dien cua RANDOM GREEDY duoc cai thien:
  - residual `f(O union A_i)` khong suy giam xau nhu unguided case;
  - gain recurrence cho `f(A_i)` tot hon ve cuoi qua trinh.
- Paper giai he recurrence nay de ra cac constant `0.385` va `0.305`.
- Phan deterministic thay RANDOM GREEDY bang INTERPOLATED GREEDY vi no de derandomize hon.
- Phan nearly-linear dung quan sat rang ngay ca khi interpolated greedy gap near-worst-case behavior, no van sinh duoc mot guidance set kha tot.

## Key Techniques

- fast local search guidance sets
- guided random greedy
- guided interpolated greedy
- blended / mixed marginal-gain recurrences
- derandomization thong qua interpolated greedy
- reusing partial greedy information de tao guidance ma khong can local search day du

## Key Lemmas Or Structural Claims

- Theorem 2.1: randomized `0.385 - epsilon` cho size va `0.305 - epsilon` cho matroid trong `O(kn / epsilon)` queries.
- Lemma 2.2: FAST LS tao `((1 + epsilon) alpha, alpha)`-guidance set.
- Recurrences moi cho guided random greedy la xuong song cua ratio vuot `1 / e`.
- Phan appendix dua deterministic va nearly-linear variants.

## Delicate Points / Caveats

- Paper rat rong: main text chi sketch size-constraint proof, con matroid, deterministic, va nearly-linear phan lon nam o appendix.
- Constant `0.385` bang state-of-the-art continuous ratio luc do, nhung dat duoc bang combinatorial machinery khac hoan toan.
- Nearly-linear ratio `0.377` la nho hon `0.385`; no la tradeoff de lay query complexity thap hon.

## Extraction To Concepts

- Chua can tao concept note rieng, nhung synthesis `submodular` nen co nhanh `guided combinatorial beyond 1/e`.
- Reusable ingredient ro nhat la "guidance set + guided greedy" cho non-monotone constrained submodular.

## Extraction To Syntheses

- `syntheses/submodular.md` nen them paper nay nhu moc ly thuyet cua combinatorial beyond-`1 / e`.
- Paper nen duoc dat canh Tukan 2024 va Chen et al. 2025 de tao cum `guided / interlaced / parallel` cho non-monotone line.

## Weaknesses / Limits

- Practical size van kem hon paper practical chuyen biet cho cardinality.
- Proof va pseudocode day du phan tan nhieu appendix, lam retrieval kho neu khong co canonical note sau.