# Liu et al. 2020 - Submodular Optimization Problems and Greedy Strategies: A Survey

## One-paragraph Summary

Survey nay rat co gia tri cho repo vi no khong chi noi "greedy dat `1 - 1/e`". No trinh bay greedy nhu mot ho ky thuat rong, trong do curvature, batched decisions, group decisions, string submodularity, va decentralized settings deu co mot phien ban phan tich rieng. Neu Nemhauser-Wolsey-Fisher la goc, thi Liu et al. la ban do cho cac nhanh mo rong cua greedy.

## Classification Rationale

Paper thuoc `submodular`, danh dau `survey`, va tap trung vao `greedy strategies`. No giao thoa voi `curvature analysis`, `string submodularity`, `batched greedy`, va cac setting game / distributed.

## Setup

- Domain / model: survey tren nhieu lop bai toan submodular, chu yeu quanh set-submodular va string-submodular optimization.
- Oracle / access model: tong hop nhieu setting phan tich greedy thay vi mot mo hinh duy nhat.
- Assumptions: thay doi theo moi nhanh; diem chung la tim performance guarantees cho greedy va cac bien the.

## Main Results

1. Survey tong hop cac performance bounds cua greedy trong bai toan submodular optimization co dien.
2. No mo rong buc tranh sang curvature-based bounds, `k`-batch / group greedy, string-submodularity, va mot so setting equilibrium / distributed.
3. Survey cho mot vocabulary rat huu ich de gan nhan cac guarantee: total curvature, partial curvature, batched curvature, group curvature, v.v.

## Core Algorithmic Idea

Khong co mot thuat toan moi; dong gop cua survey la cho thay greedy khong phai mot object don le ma la mot pattern phan tich. Neu biet dai luong nao do do "muc do xa khoi modular", thi ta thuong co the thay `1 - 1/e` bang mot bound sac hon phu thuoc curvature. Day la truc giac chinh can luu lai.

## Proof / Analysis Strategy

- Buoc 1: bat dau tu greedy co dien va bound residual-gap kieu Nemhauser-Wolsey-Fisher.
- Buoc 2: gioi thieu cac dai luong curvature / structure do muc do diminishing returns, va viet lai performance bounds theo cac dai luong nay.
- Buoc 3: tong quat hoa sang quyet dinh theo block, theo chuoi, hoac theo nhieu agent, cho thay cung mot khung phan tich co the song trong nhieu setting.

## Key Techniques

- curvature-based refinement cua greedy bounds
- survey cua batched / grouped greedy
- string-submodularity viewpoint
- mapping tu set-submodular greedy sang cac bien the mo rong

## Key Lemmas Or Structural Claims

- Hieu nang greedy co the duoc tham so hoa bang curvature, khong nhat thiet chi bang worst-case `1 - 1/e`.
- Khi quyet dinh theo block / group, can mot notion curvature phu hop hon so voi case tung phan tu.
- String-submodularity cung cho phep mot dang diminishing returns, nhung tren thu tu / sequence thay vi tap.

## Delicate Points / Caveats

- Survey hop nhat nhieu notations curvature khac nhau; can doc ky xem moi dai luong duoc dinh nghia trong setting nao.
- Khong nen gom tat ca cac bounds thanh mot thong diep "curvature cai thien greedy"; moi setting co mot dieu kien khac nhau.
- Day la survey nghieng ve bounds, khong phai tong quan day du moi nhanh algorithmic cua submodular optimization.

## Extraction To Concepts

- Dinh nghia / notation nen dua vao `concepts/`: total curvature, partial curvature, batched greedy, string submodularity, group curvature.
- Lemma co the tai su dung: performance of greedy can be sharpened by structural parameters.
- Technique lap lai: thay worst-case residual bound bang residual bound co tham so curvature.
- Quan he voi nhom khac: huu ich de so sanh greedy guarantee tren submodular, k-submodular, va co the ca DR settings.

## Extraction To Syntheses

- Cap nhat `syntheses/submodular.md` trong nhanh greedy / surveys / curvature.
- `syntheses/k-submodular.md` co the nhac survey nay nhu bo tu vung de hoi "co curvature notion nao cho k-submodular khong".
- `syntheses/dr-submodular.md` co the nhac khi tim analog curvature tren lattice / continuous domains.
- `syntheses/mixed.md` co the them mot note ve "greedy as a transferable proof pattern".

## Weaknesses / Limits

- Survey rong, nen khong di sau tung proof.
- Tap trung vao greedy bounds, nen nhung nhanh khac nhu multilinear / continuous methods khong phai trong tam.

## Research Ideas Triggered

- Tao mot concept cluster rieng cho curvature va gan no vao cac paper greedy trong repo.
- Theo doi xem notions curvature nao co analog hop ly tren k-submodular hoac DR-submodular domains.