# Nemhauser, Wolsey, Fisher 1978 - Maximizing Submodular Set Functions

## One-paragraph Summary

Day la paper nen tang cua approximation cho monotone submodular maximization. Dong gop kinh dien nhat la phan tich greedy duoi rang buoc cardinality, trong do moi buoc greedy thu duoc it nhat mot phan `1/K` cua gia tri con thieu so voi nghiem toi uu. Tu recurrence nay, paper rut ra guarantee tien ve `1 - 1/e`, bien greedy thanh mot baseline chuan cho nhieu huong sau nay: streaming, adaptive variants, va ca cac mo rong tren domain phong phu hon.

## Classification Rationale

Paper nam trong `submodular` vi doi tuong trung tam la monotone set-submodular maximization. No giao thoa voi `approximation algorithms`, `greedy analysis`, va la moc lich su de so sanh khi nghien cuu `k-submodular` hoac `DR-submodular` maximization.

## Setup

- Domain / model: ham `f : 2^V -> R_+`, thuong duoc gia dinh khong giam va submodular.
- Oracle / access model: value-oracle / set-function analysis co dien.
- Assumptions: rang buoc chinh la `|S| <= K`; paper con ban them ve local improvement va cac formulation lien quan.

## Main Results

1. Greedy theo marginal gain cho monotone submodular maximization duoi rang buoc cardinality co bound `1 - (1 - 1/K)^K`, va do do dat nguong `1 - 1/e` khi `K` lon.
2. Paper phan tich them cac bien the nhu `R`-stage greedy va interchange heuristic de so sanh suc manh cua cac chien luoc local.
3. No dat nen tang cho cach phan tich approximation bang "residual value" thay vi bang exchange thuan tuy.

## Core Algorithmic Idea

Thuat toan cot loi rat don gian: bat dau tu tap rong, moi buoc them phan tu co marginal gain lon nhat. Diem sau sac khong nam o thuat toan, ma o cach paper gap recurrence: neu `S_i` la tap sau `i` buoc va `O` la nghiem toi uu kich thuoc `K`, thi nhin trung binh marginal cua cac phan tu trong `O \\ S_i` se suy ra ton tai it nhat mot phan tu cho muc tang bang mot phan hang so cua residual `f(O) - f(S_i)`.

## Proof / Analysis Strategy

- Buoc 1: dung submodularity de cho thay tong marginal cua cac phan tu trong nghiem toi uu, do tren nen `S_i`, khong the nho hon residual toward OPT.
- Buoc 2: vi co toi da `K` phan tu can xet, ton tai mot phan tu co marginal gain it nhat bang residual chia `K`.
- Buoc 3: do greedy chon phan tu tot nhat, no cung dat muc gain nay; lap recurrence qua `K` buoc de thu duoc bound dang mu / `1 - 1/e`.

## Key Techniques

- residual-value recurrence cho greedy
- averaging argument tren cac marginal cua nghiem toi uu
- dung diminishing returns de "telecope" khoang cach toi OPT
- so sanh greedy voi local-search / LP viewpoints

## Key Lemmas Or Structural Claims

- `f(S_{i+1}) - f(S_i)` duoc lower-bound boi mot phan hang so cua `f(O) - f(S_i)`.
- Tong marginal khi them cac phan tu cua OPT vao `S_i` upper-bounds / lower-bounds residual nho submodularity va monotonicity.
- Recurrence tuyen tinh tren residual giai ra bound co dang `1 - (1 - 1/K)^i`.

## Delicate Points / Caveats

- Guarantee kinh dien can monotonicity; nonmonotone maximization la mot the gioi khac.
- Day la rang buoc cardinality co ban; khi sang matroid, knapsack, hay streaming, proof spine thay doi du khung greedy van con.
- Nhiem vu cua paper la worst-case analysis; khong nen doc no nhu bai ve practical heuristics du data-driven.

## Extraction To Concepts

- Dinh nghia / notation nen dua vao `concepts/`: residual-greedy recurrence, monotone submodular cardinality maximization, `1 - 1/e` lineage.
- Lemma co the tai su dung: average marginal of OPT elements controls residual gap.
- Technique lap lai: "compare one greedy step to a fraction of OPT" la mau so chung cho rat nhieu proof sau nay.
- Quan he voi nhom khac: day la to tien truc tiep cua streaming thresholding va randomized greedy comparison arguments.

## Extraction To Syntheses

- Cap nhat `syntheses/submodular.md` lam paper foundation cho maximization.
- `syntheses/k-submodular.md` nen nhac paper nay nhu baseline de thay phan thuong bi giam khi domain phong phu hon.
- `syntheses/dr-submodular.md` nen nhac y tuong residual-gap vi no thuong tai xuat hien duoi dang threshold / continuous variants.
- `syntheses/mixed.md` co the them mot note rieng ve "greedy lineage".

## Weaknesses / Limits

- Khong bao quat nonmonotone, online, streaming, hay rang buoc phuc tap.
- Voi nguoi da quen ket qua `1 - 1/e`, paper de bi doc luot qua va bo qua proof spine; nhung chinh proof spine moi la phan can giu lai.

## Research Ideas Triggered

- Lap mot note so sanh "mot buoc greedy an duoc bao nhieu residual" giua set-submodular, k-submodular, va DR-submodular.
- Theo doi nhung no luc vuot qua greedy don gian: local search, multilinear / continuous methods, va threshold streaming.