# Chen et al. 2025 - Breaking Barriers: Combinatorial Algorithms for Non-monotone Submodular Maximization with Sublinear Adaptivity and 1/e Approximation

## One-paragraph Summary

Day la paper parallel quan trong cho non-monotone submodular maximization duoi size constraint. Dong gop chinh la lan dau tien co combinatorial algorithm dat `1 / e - epsilon` trong che do sublinear adaptivity, truoc do moc nay chi co continuous algorithm. Paper khong chi song song hoa mot greedy co san, ma con sua lai ca interlaced / interpolated greedy backbone de bo nhung buoc guessing branch kho parallelize. Tu do, paper dua ra hai algorithm:

- `PIG`: `(1/4 - epsilon)` voi high probability;
- `PITG`: `1 / e - epsilon` theo expectation.

Ca hai deu dat `O(log n log k)` adaptivity va query complexity gan `O(n log n log k)` theo `epsilon`.

## Classification Rationale

Paper thuoc `submodular`, non-monotone, cardinality-constrained, parallel / adaptivity. No noi tiep hai nhanh:

- interlaced / interpolated greedy cua Kuhnle va Chen-Kuhnle;
- practical parallel algorithms, noi tu combinatorial line sang sublinear-adaptivity line.

Ve retrieval, no la counterpart parallel cua cum papers `beyond 1 / e` trong repo.

## Setup

- Objective: non-negative submodular maximization, khong gia su monotone.
- Constraint: cardinality `k`.
- Model: parallel query model, do bang adaptivity.
- Targets: combinatorial, nearly-linear query complexity, logarithmic adaptivity.

## Main Results

1. Theorem 3.1: simplified `INTERPOLATEDGREEDY` dat `1 / e - epsilon` voi `O(kn / epsilon)` queries va success probability `1`, bo duoc probabilistic branching cua ban truoc.
2. Theorem 4.1: `PARALLELINTERLACEGREEDY` dat `(1/4 - epsilon)` voi high probability, `O(log n log k)` adaptivity, `O(n log n log k)` queries up to epsilon factors.
3. Theorem 4.2: `PARALLELINTERPOLATEDGREEDY` dat `1 / e - epsilon`, cung logarithmic adaptivity va nearly-linear query complexity.

## Core Algorithmic Idea

Paper co hai tang y tuong.

- Tang 1: `blended marginal gains`.
  Simplify `INTERPOLATEDGREEDY` bang cach khong con phai duy tri nhieu branch de doan singleton / vi tri dung trong optimum. Thay vao do, paper phan tich tong hop marginal gains qua nhieu solutions trong mot "single pool", van khien duoc recurrence `1 / e`.

- Tang 2: `parallel threshold sampling`.
  De parallelize interlaced greedy, paper xay `PIG`:
  - duy tri nhieu solution sets song song;
  - dung threshold sampling de them ca batch phan tu;
  - dong bo kich thuoc batch giua cac solution de giu alternating-selection structure.

`PITG` dat `1 / e - epsilon` bang cach goi lap lai `PIG` trong outer loop tuong tu simplified interpolated greedy.

## Proof / Analysis Strategy

- Cho simplified interpolated greedy, paper dung partition cua optimum thanh `O_1, ..., O_l` va phan tich hai loai term:
  - self-interaction `Delta(O_l | A_l)`;
  - cross-interaction `Delta(O_{l1} | A_{l2}) + Delta(O_{l2} | A_{l1})`.
- `Blended marginal gains` cho upper bound tot hon tren cross terms, thay cho branching guess cu. Tu do suy ra recurrence tong quat dan den `1 / e - epsilon`.
- Cho `PIG`, paper dung threshold sampling va mot loat lemmas de giu ba thu cung luc:
  - cac candidate sets van pairwise disjoint;
  - moi batch them vao van co average marginal gain du lon;
  - candidate pools co the loc nhanh theo threshold de lay sublinear adaptivity.
- Cho `PITG`, lap recurrence tu `PIG` theo outer loop, giong spine cua simplified interpolated greedy.

## Key Techniques

- blended marginal gains
- simplified interpolated greedy without branching guesses
- parallel threshold sampling
- synchronized batch construction across interlaced solutions
- unified PIG subroutine for both `1/4` and `1 / e` parallel algorithms

## Key Lemmas Or Structural Claims

- Theorem 3.1: simplified interpolated greedy dat `1 / e - epsilon`.
- Claim 3.1 / Lemma 3.2: partition optimum va upper bound self/cross interactions.
- Theorem 4.1: `PIG` dat `(1/4 - epsilon)` w.h.p.
- Theorem 4.2: `PITG` dat `1 / e - epsilon`.

## Delicate Points / Caveats

- Paper chi xu ly size constraint, khong xu ly matroid.
- Query / adaptivity formulas trong paper co nhieu he so `epsilon` chi tiet; canonical note nen giu spine chinh hon la moi mu.
- Phan simplified serial algorithms va phan parallel algorithms gan nhau ve tu duy, nhung pseudocode / proofs tach thanh nhieu appendix.

## Extraction To Concepts

- Chua can tao concept note rieng, nhung `syntheses/submodular.md` nen them nhanh `parallel interlaced / interpolated greedy`.
- Reusable ingredient moi la blended marginal gains, co the quan trong neu sau nay co them papers parallel / interlaced.

## Extraction To Syntheses

- Paper nay la moc cho parallel combinatorial `1 / e`.
- Nen dat canh Chen et al. 2024 va Tukan et al. 2024 de thay ba huong: ly thuyet combinatorial rong, practical size-only, va parallel sublinear-adaptivity.

## Weaknesses / Limits

- Khong mo rong sang matroid hay knapsack.
- Guarantee `1 / e - epsilon` la expectation; ban `(1/4 - epsilon)` moi la high-probability simpler route.