# Schrijver 2000 - A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time

## One-paragraph Summary

Day la paper cot moc cua submodular function minimization (SFM): no chung minh bai toan co the giai bang thuat toan hoan toan combinatorial trong strongly polynomial time, khong can dua vao ellipsoid va khong phu thuoc vao do lon so hoc cua gia tri ham. Gia tri cua paper trong repo la o cho no dong khung minimization nhu mot bai toan polyhedral / base-polytope co the giai bang exchange va augmenting-style arguments, noi Edmonds voi cac survey va ket qua sau nay.

## Classification Rationale

Paper thuoc `submodular` va nam trong nhanh `minimization`. No giao thoa cuc manh voi `polyhedral combinatorics`, `base polyhedron`, `exchange algorithms`, va la mot paper can doc ky neu muon hieu vi sao SFM co the tro thanh bai toan thuan combinatorial.

## Setup

- Domain / model: submodular set function `f : 2^V -> R`, muc tieu tim tap `X` toi thieu hoa `f(X)`.
- Oracle / access model: oracle cho gia tri cua `f`, ket hop voi cac primitive combinatorial sinh extreme bases.
- Assumptions: khong dua vao bit-length cua gia tri `f` trong complexity; khai thac base polyhedron lien ket voi `f`.

## Main Results

1. Paper dua ra mot strongly polynomial combinatorial algorithm cho SFM.
2. Thuat toan loai bo su le thuoc vao phuong phap ellipsoid va cac bounds so hoc cua literature truoc.
3. No xay duoc mot tieu chuan chung nhan minimizer thong qua cau truc tren base polyhedron va mot do thi / he quan he giua cac phan tu.

## Core Algorithmic Idea

Y tuong cot loi la khong toi uu hoa truc tiep tren tap, ma di chuyen tren base polyhedron cua `f`. Tu cac extreme base sinh bang greedy orderings, paper duy tri / cai thien mot cau hinh cho phep hoac la (i) tien them mot buoc exchange / augmentation de cai thien chung nhan hien tai, hoac (ii) ket luan da tim thay tap minimizer khi cau truc do thi lien quan khong con duong "augmenting" thich hop. Tinh than cua paper rat giong max-flow / push-relabel o muc cau truc, du doi tuong la submodular polyhedron.

## Proof / Analysis Strategy

- Buoc 1: dua SFM ve mot bai toan tren base polyhedron, noi gia tri cua tap voi cac vector base va cac tight sets.
- Buoc 2: xay mot quy trinh cap nhat combinatorial dua tren extreme bases greedy, exchange capacities, va cac quan he co huong giua phan tu.
- Buoc 3: chung minh moi lan cap nhat hoac cai thien mot potential nao do, hoac tao ra mot certificate rang tap tight / closure hien tai la minimizer; tu do suy ra strongly polynomial termination.

## Key Techniques

- base-polyhedron viewpoint cho SFM
- extreme bases sinh bang greedy permutations
- augmenting-path / exchange-capacity reasoning
- strong polynomiality qua potential reduction thuan combinatorial

## Key Lemmas Or Structural Claims

- Minimizer cua `f` co the doc ra tu structure cua mot nghiem tren base polyhedron va cac tight sets.
- Extreme bases cua base polyhedron co the sinh hieu qua bang greedy tren permutations.
- Neu khong con duong / exchange hop le tu phan duong sang phan am trong cau truc hien tai, thi mot tap dong duoc xac dinh la minimizer.

## Delicate Points / Caveats

- Day la paper kho; neu doc lien tuc tung lemma rat de mat buc tranh lon. Nen giu spine: `base polyhedron -> exchange structure -> certificate of optimality`.
- Mot so truc giac "augmenting path" la analog combinatorial, khong phai dung max-flow theo nghia den.
- Paper la theory paper nang; doi voi repo tham khao, dieu quan trong nhat la nho vai tro cua base polyhedron va certificate, khong nhat thiet tai tao toan bo complexity proof.

## Extraction To Concepts

- Dinh nghia / notation nen dua vao `concepts/`: base polyhedron, extreme base, tight set, optimality certificate trong SFM.
- Lemma co the tai su dung: khong con exchange / augmenting structure thi co minimizer.
- Technique lap lai: encode minimization bang polyhedral geometry roi dung exchange algorithm.
- Quan he voi nhom khac: day la nhanh song song voi Lovasz-extension / ellipsoid viewpoint trong SFM.

## Extraction To Syntheses

- Cap nhat `syntheses/submodular.md` lam moc minimization / strongly polynomial SFM.
- `syntheses/k-submodular.md` khong cap nhat truc tiep.
- `syntheses/dr-submodular.md` khong cap nhat truc tiep.
- `syntheses/mixed.md` co the them mot note ve "polyhedral proofs vs approximation proofs".

## Weaknesses / Limits

- Rat kho doc neu chua quen base polyhedron; khong phai paper vao cua nguoi moi.
- Mac du cuc ky quan trong ve ly thuyet, paper khong phai nguon tot nhat de hoc tat ca truc giac SFM tu dau.

## Research Ideas Triggered

- Tao mot note doi chieu Schrijver voi Cunningham, Iwata-Fleischer-Fujishige, va Orlin theo truc "cai gi la certificate trung tam".
- Kiem tra xem co analog "exchange certificate" nao trong k-submodular hoac DR-submodular minimization khong.