# McCormick 2007 - On Submodular Function Minimization

## One-paragraph Summary

McCormick la survey / tutorial rat hop de giu trong repo vi no giai thich SFM theo goc nhin de vao hon Iwata. Neu Iwata co xu huong "ban do ly thuyet", thi McCormick co xu huong "guide cho nguoi doc": bai toan la gi, xuat hien o dau, co nhung ho thuat toan nao, va vi sao moi ho lai quan trong. Gia tri cua file nay la giup cac thread sau nhanh chong dinh vi mot paper SFM moi vao dung nhanh.

## Classification Rationale

Paper thuoc `submodular`, danh dau `survey`, va nam o nhanh `minimization`. No giao thoa voi `tutorial exposition`, `algorithm taxonomy`, va phu hop de dung nhu note chi duong trong cum SFM.

## Setup

- Domain / model: survey ve submodular function minimization va cac ung dung lien quan.
- Oracle / access model: trinh bay nhieu mo hinh thuat toan va quan he giua chung.
- Assumptions: huong toi doc gia muon hieu landscape hon la theo doi mot theorem moi duy nhat.

## Main Results

1. Survey giai thich dong co va cac ung dung co dien cua SFM.
2. No tong hop cac ho thuat toan va dat chung canh nhau theo muc de hieu: ellipsoid, Cunningham-type, Schrijver-type, ring families, va cac huong combinatorial khac.
3. Paper rat huu ich de lam index doc literature, dac biet khi can quyet dinh nen doc paper goc nao tiep theo.

## Core Algorithmic Idea

Khong co algorithm moi, nhung co mot "editorial algorithm" rat gia tri: muon hieu SFM, hay nhom paper theo certificate / structure ma chung thao tac, thay vi nho theo thu tu lich su. Cach to chuc cua McCormick de tao ra note tham khao nhanh cho repo vi no uu tien dinh huong va so sanh.

## Proof / Analysis Strategy

- Buoc 1: gioi thieu bai toan va vi sao minimization khac voi maximization trong submodular world.
- Buoc 2: nhom literature theo cac ho thuat toan va mo ta y tuong cot loi cua tung ho.
- Buoc 3: dat cac huong canh nhau de nguoi doc thay trade-off giua tinh combinatorial, do phuc tap implementation, va muc do ly thuyet.

## Key Techniques

- tutorial-style synthesis
- algorithm family comparison
- ung dung nhu index / landing note
- emphasis on certificates and structure over single theorem

## Key Lemmas Or Structural Claims

- Khong co lemma moi trung tam; dong gop la cach gom cum literature.
- SFM nen duoc doc qua cac doi tuong chung nhu base polyhedron, ring family, va combinatorial certificates.
- Nhieu ho thuat toan tuong nhu khac nhau, nhung chia se cung nhung structure goc.

## Delicate Points / Caveats

- Khong nen dung survey nay de trich dan theorem chi tiet neu da co paper goc.
- Vi tinh tutorial, mot so ratio / complexity details duoc lam nhe de giu dong chay exposition.
- Gia tri cua survey khong nam o "moi", ma o "de dung" va "de dinh vi".

## Extraction To Concepts

- Dinh nghia / notation nen dua vao `concepts/`: SFM algorithm families, ring family viewpoint, minimization certificates.
- Lemma co the tai su dung: khong co lemma moi; thay vao do la taxonomy de danh chi muc.
- Technique lap lai: to chuc note theo "paper giai quyet bang cau truc nao".
- Quan he voi nhom khac: tot de noi Iwata survey voi paper minimization goc.

## Extraction To Syntheses

- Cap nhat `syntheses/submodular.md` nhu tutorial entry point cho minimization.
- `syntheses/mixed.md` co the nhac survey nay nhu note chi duong cho nguoi moi vao cum SFM.
- `syntheses/k-submodular.md` va `syntheses/dr-submodular.md` khong can cap nhat truc tiep.

## Weaknesses / Limits

- Khong thay the duoc paper goc khi can chi tiet complexity / proof.
- It "structural depth" hon Iwata neu muc tieu la discrete convexity viewpoint.

## Research Ideas Triggered

- Tao mot note doi chieu Iwata vs McCormick: survey nao tot cho "structure", survey nao tot cho "navigation".
- Dung taxonomy cua McCormick lam schema phu cho nhom minimization trong repo.