# Chen, Kuhnle 2020 - Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint

## One-paragraph Summary

Day la paper quan trong trong nhanh `non-monotone submodular maximization` duoi cardinality khi muc tieu chinh la vua parallelize tot vua giu query complexity gan tuyen tinh. Paper sua mot lo hong cua conference version: threshold-sampling cu khong hop le cho non-monotone objectives. Thay vao do, tac gia thiet ke `ThreshSeq`, mot subroutine co high-probability guarantee va chi can `O(n)` queries, `O(log n)` adaptivity. Tren backbone do, paper dua ra hai algorithm chinh: `AST` voi ratio `1 / 6 - eps` va `ATG` voi ratio `0.193 - eps`, deu giu query complexity `O(n log k)` nhung phan biet nhau o so adaptive rounds.

## Setup

- Objective: non-negative submodular function `f : 2^N -> R_+`, khong gia su monotone.
- Constraint: `|S| <= k`.
- Model: value oracle, do hai tai nguyen chinh la query complexity va adaptivity.

## Main Results

1. `ThreshSeq` giai duoc threshold subproblem cho non-monotone objectives voi `O(n)` queries ky vong va `O(log(n / delta))` adaptivity.
2. `AdaptiveSimpleThreshold (AST)` dat ratio `1 / (4 + alpha) - eps`; ghep voi unconstrained `1 / 2 - eps` cho ra `1 / 6 - eps`.
3. `AdaptiveThresholdGreedy (ATG)` dat `0.193 - eps` voi `O(log n log k)` adaptivity va `O(n log k)` queries.
4. Paper chi ro conference version cu dung mot threshold-sampling sai cho non-monotone functions; `ThreshSeq` la sua chua ky thuat chinh.

## Core Algorithmic Idea

`ThreshSeq` tach vai tro cua tap threshold thanh hai doi tuong:

- `A`: tap lon hon, dung de filtering candidate set va xac dinh khi khong con phan tu vuot threshold;
- `A'`: tap con "tot" cua `A`, chi giu nhung phan tu co marginal gain du lon de bao toan objective value.

Tren subroutine do:

- `AST` doan threshold `tau`, chay `ThreshSeq` hai lan tren hai residuals, roi goi unconstrained maximization de hoi phuc mot mien gia tri bi threshold bo sot.
- `ATG` la adaptive version cua iterated greedy, thay greedy exact bang low-adaptivity thresholded blocks va phan tich moi de nang constant len `0.193`.

## Proof / Analysis Strategy

- `ThreshSeq` dam bao `f(A') >= (1 - eps) tau |A|`, va neu `|A| < k` thi khong con phan tu vuot `tau`.
- `AST` decomposition `OPT` thanh vai mien ma hoac duoc threshold capture, hoac duoc unconstrained subroutine hoi phuc.
- `ATG` mo phong iterated greedy bang threshold schedules, roi dung novel analysis de cai thien he so.

## Key Techniques

- non-monotone threshold sampling voi hai tap `A, A'`
- high-probability threshold guarantees
- unconstrained subproblem plugging
- adaptive threshold schedules

## Delicate Points / Caveats

- Ban `v5` da sua bug nghiem trong cua conference version; note nay can duoc doc nhu canonical ban dung.
- Chi cho size constraint, khong tu dong mo rong sang knapsack hay matroid.
- `0.193` van thap hon line `0.385`; gia tri chinh la tradeoff song song + gan-tuyen-tinh queries.

## Extraction To Concepts

- Chua can concept note rieng; phan reusable nen dua vao `syntheses/submodular.md` duoi nhanh threshold / adaptivity.

## Extraction To Syntheses

- `syntheses/submodular.md` nen bo sung paper nay vao low-adaptivity non-monotone cardinality line.

## Weaknesses / Limits

- Khong dat ratio frontier tot nhat.
- Phai ghep voi unconstrained solver ngoai.