# Chen, Dey, Kuhnle 2021 - Optimal Submodular Maximization in Parallel

## One-paragraph Summary

Day la paper parallel cho monotone cardinality-constrained submodular maximization, nham dat dong thoi ba muc tieu: approximation gan toi uu `1 - 1 / e`, adaptivity logarithmic, va query complexity tuyen tinh theo `n`. Paper dat muc tieu do bang `LS+PGB`, mot khung ket hop ba thanh phan:

- `LINEAR SEQ` de lay mot constant-factor solution / narrow interval chua `OPT`;
- `THRESHOLD SEQ` de them ca lo phan tu vuot nguong trong it adaptive rounds;
- `PARALLEL GREEDY BOOST` de nang constant factor thanh `1 - 1 / e - eps`.

Ban `v3` dong thoi sua hai loi phan tich o version truoc, nen day la canonical version nen doc.

## Setup

- Objective: monotone submodular `f : 2^N -> R_+`.
- Constraint: `|S| <= k`.
- Model: adaptive complexity.
- Muc tieu: constant / near-optimal approximation trong expected `O(n)` queries va `O(log n)` rounds.

## Main Results

1. `LINEAR SEQ` dat constant-factor approximation gan `1 / 4`, expected `O(n)` queries, va `O(log n)` adaptivity.
2. `THRESHOLD SEQ` them tap phan tu co gain tren nguong `tau` trong `O(log n)` adaptivity va expected `O(n)` queries.
3. `LS+PGB` dat approximation `1 - 1 / e - eps`, `O(log n)` adaptivity, va expected `O(n)` queries.

## Core Algorithmic Idea

### `LINEAR SEQ`

- bo cac phan tu co marginal gain nho hon `f(A) / k`;
- hoan vi ngau nhien candidate set con lai;
- query song song cac block prefix;
- them mot prefix "du tot" vao nghiem `A`;
- dong thoi dam bao se bo duoc mot phan hang so candidate o vong sau.

### `THRESHOLD SEQ`

- giong triet ly `LINEAR SEQ`, nhung thay vi uoc luong `OPT`, no giai task co dinh: lay tat ca phan tu co gain vuot `tau`.

### `PARALLEL GREEDY BOOST`

- khoi tao threshold bang `Gamma / k`, trong do `Gamma` den tu `LINEAR SEQ`;
- lap threshold schedule giam dan;
- moi muc nguong goi `THRESHOLD SEQ` tren residual function;
- recurrence residual-gap dua tong gia tri dat den `1 - 1 / e - eps`.

## Proof / Analysis Strategy

- `LINEAR SEQ` can bang hai muc tieu trong cung mot prefix: moi cap nhat phai giu average gain du lon va cung giup bo duoc nhieu phan tu.
- `THRESHOLD SEQ` dam bao neu stop som thi tat ca phan tu con lai deu duoi threshold.
- `PGB` dung `Gamma` tu constant-factor solution lam lower bound dau, roi threshold schedule duoc chon de recurrence residual-gap tro thanh analogue cua greedy optimum `1 - 1 / e`.

## Key Techniques

- linear-query preprocessing
- random block-prefix selection
- parallel thresholding
- boosting from constant-factor to near-optimal

## Delicate Points / Caveats

- Ban `v3` cua paper tu ghi ro version cu co hai loi:
  - co the them "bad block" gay mat objective;
  - dung sai Wald's equation trong phan tich `LINEAR SEQ`.
- Paper chi xu ly monotone cardinality case.

## Extraction To Concepts

- `concepts/linear-query-submodular-maximization.md` nen coi paper nay la partner parallel cua `exactly-n query` line.

## Extraction To Syntheses

- Them paper nay vao `syntheses/submodular.md` trong nhom core papers parallel / adaptivity.

## Weaknesses / Limits

- Chi cho monotone cardinality.
- Khong xu ly non-monotone / matroid / knapsack.