# Breuer, Balkanski, Singer 2019 - The Fast Algorithm for Submodular Maximization

## One-paragraph Summary

Paper nay dat muc tieu ro rang: bien low-adaptivity monotone submodular maximization thanh thu gi do co the chay duoc trong thuc te. Ket qua la `FAST` (Fast Adaptive Sequencing Technique), van giu ratio `1 - 1 / e - eps` cho cardinality, nhung query complexity chi `O(n log log k)` va adaptivity `O(log n * log^2 log k)`, dong thoi toan bo thiet ke duoc toi uu de tranh cac hang so lon cua adaptive-sampling papers truoc do. Y nghia cua paper khong nam o moc xap xi moi, ma o cho no bien "parallel logarithmic" thanh mot algorithm practical.

## Setup

- Objective: monotone submodular `f : 2^N -> R_+`.
- Constraint: `|S| <= k`.
- Muc tieu: it rounds song song, tong so queries it, va constants nho de chay nhanh tren data lon.

## Main Results

1. Theorem 1:
   voi tham so `eps, delta`, `FAST` dat `1 - 1 / e - O(eps)` voi high probability.
2. Complexity:
   `O(log n * log^2 log k)` adaptivity va `O(n log log k)` queries.
3. Experiment:
   trong cac benchmark duoc bao cao, `FAST` nhanh hon ro rang so voi `Amortized-Filtering`, `Exhaustive-Maximization`, `Randomized-Parallel-Greedy`, va ca `Parallel-LTLG`.

## Core Algorithmic Idea

- Dung adaptive sequencing thay vi adaptive sampling:
  - sinh mot random sequence cua cac phan tu chua bi loai;
  - tim prefix lon nhat ma sau khi them prefix do, van co "nhieu" phan tu con marginal cao;
  - bo nhung phan tu marginal thap.
- Hai cho phai binary search:
  - doan OPT;
  - doan vi tri prefix `i*`.
- Them mot loat heuristics / optimizations de practical hon:
  - preprocessing nhung phan tu sequence co marginal cao se duoc them ngay;
  - lazy updates cho marginal;
  - thuong chi can mot guess duy nhat cho OPT.

## Proof / Analysis Strategy

- Vanilla adaptive sequencing cho ratio `1 - 1 / e - O(eps)` nhung con query complexity `O(nk)`.
- Binary search tren guesses cua OPT cat query phu thuoc `k`.
- Binary search tren prefix positions cat tiep query complexity tu `O(nk)` xuong `O(n log log k)`.
- High-probability robust guarantee can thiet vi algorithm binary search tren nhieu runs; paper generalize robust guarantees de binary search van dung.
- Adaptive complexity duoc kiem soat boi su kien moi iteration loai bo duoc it nhat mot `eps` fraction cua set surviving.

## Key Techniques

- adaptive sequencing
- binary search over OPT
- binary search over prefix positions
- sample a small subset of surviving elements
- preprocessing high-value elements
- lazy marginal updates
- high-probability robust guarantee

## Delicate Points / Caveats

- Paper chi xu ly monotone cardinality case, khong phai non-monotone hay matroid.
- Dong gop la practical engineering + fine-grained complexity design, khong phai moc approximation moi.
- Cac benchmark song song rat duoc nhan manh; can doc paper sau do neu muon gap tight ly thuyet hon trong parallel model.

## Extraction To Concepts

- `concepts/greedy-cardinality-approximation.md` khong nhat thiet mo rong, nhung `syntheses/submodular.md` nen nhan manh nhanh practical low-adaptivity song song.

## Extraction To Syntheses

- `syntheses/submodular.md` nen them FAST vao parallel/practical cardinality line, tach biet voi line theory-optimal cua Chen-Dey-Kuhnle va line beyond-`1/e`.