# Iwata 2007 - Submodular Function Minimization

## One-paragraph Summary

Day la survey nen doc de nhin toan canh nhanh minimization truoc khi lao vao cac paper nang nhu Schrijver. Gia tri cua no nam o cach sap xep SFM thanh mot linh vuc co ba lop ro rang: (i) cau truc va analog voi convexity, (ii) phuong phap ellipsoid / Lovasz extension, va (iii) cac thuat toan combinatorial. No khong dong gop mot theorem moi cho repo, nhung la "landing note" rat tot de noi foundation polyhedral voi literature minimization hien dai.

## Classification Rationale

Paper thuoc `submodular` va duoc danh dau `survey`, tap trung vao `minimization`. No giao thoa voi `discrete convexity`, `polyhedral methods`, va `algorithm landscape`.

## Setup

- Domain / model: survey ve submodular set functions, nhat la bai toan minimization.
- Oracle / access model: tong hop nhieu mo hinh, tu ellipsoid / separation den combinatorial oracle algorithms.
- Assumptions: bai survey dat minimization trong boi canh tong quat cua discrete optimization, khong gioi han vao mot mo hinh duy nhat.

## Main Results

1. Survey tong hop cac tinh chat co ban cua submodularity va vi tri cua SFM trong discrete optimization.
2. No trinh bay cac nhanh giai bai toan: Lovasz extension / convexity, Cunningham-type methods, IFF / Schrijver-type combinatorial algorithms, va cac bien the lien quan.
3. Paper cho nguoi doc mot "ban do" de biet paper nao giai quyet phan nao cua SFM, thay vi chi liet ke theorem.

## Core Algorithmic Idea

Vi day la survey, khong co mot algorithm moi duy nhat. Y tuong cot loi can rut ra la cach Iwata to chuc literature: SFM khong phai mot dong ky thuat roi rac, ma la mot truong hop discrete convexity co nhieu bieu dien tuong duong. Chinh cach to chuc nay la thu can luu lai cho repo.

## Proof / Analysis Strategy

- Buoc 1: dat submodularity canh cac analog cua convexity va duality de xay truc giac chung.
- Buoc 2: nhom cac ket qua thuat toan theo cong cu chinh: ellipsoid / Lovasz, combinatorial exchange, scaling / strongly polynomial.
- Buoc 3: chi ra cac duong day lich su va quan he giua nhung huong do, de nguoi doc khong xem tung paper nhu cac mot dao rieng le.

## Key Techniques

- survey synthesis theo truc cau truc -> thuat toan
- Lovasz-extension viewpoint
- so sanh polyhedral va combinatorial methods
- dat SFM trong khung discrete convex analysis

## Key Lemmas Or Structural Claims

- Submodularity co the duoc nhin nhu analog cua convexity trong the gioi roi rac.
- Lovasz extension va base-polyhedron la hai ngon ngu trung tam de noi theory voi algorithm.
- Lich su SFM phat trien theo nhieu nhanh nhung chia se cac doi tuong structure giong nhau.

## Delicate Points / Caveats

- Day la survey nam 2007, nen khong bao gom mot so ket qua sau nay; can doc no nhu ban do den moc thoi gian do.
- Neu muc tieu la tim theorem moi de ap dung ngay, survey nay se thay "thieu"; nhung neu muc tieu la nho structure, no rat gia tri.
- Can phan biet nhung cho survey chi de dinh huong voi nhung cho trich dan ket qua chinh xac.

## Extraction To Concepts

- Dinh nghia / notation nen dua vao `concepts/`: SFM landscape, Lovasz extension, discrete convexity analogy, base polyhedron trong minimization.
- Lemma co the tai su dung: khong phai lemma moi, ma la relation map giua cac doi tuong theory.
- Technique lap lai: to chuc literature theo doi tuong structure thay vi theo nam / theo tac gia.
- Quan he voi nhom khac: giup so sanh minimization set-submodular voi mo rong sang bisubmodular va DR sau nay.

## Extraction To Syntheses

- Cap nhat `syntheses/submodular.md` lam survey cua nhanh minimization.
- `syntheses/mixed.md` co the them mot note ve "submodularity as discrete convexity".
- `syntheses/dr-submodular.md` co the nhac toi khi can doi chieu voi continuous / lattice analogies.
- `syntheses/k-submodular.md` khong can cap nhat truc tiep.

## Weaknesses / Limits

- Survey khong the thay the paper goc neu can dung chi tiet ky thuat.
- Vi co tinh tong hop, mot so phan phat bieu ngan gon hon muc can de tai tao proof.

## Research Ideas Triggered

- Dung survey nay lam note cua so vao cum SFM, roi lien ket sang Schrijver, McCormick, va Edmonds.
- Tao mot concept note rieng cho "submodularity as discrete convexity" de tai su dung trong nhieu thread sau.