# Edmonds 1970 - Submodular Functions, Matroids, and Certain Polyhedra

## One-paragraph Summary

Day la nen tang polyhedral cho gan nhu toan bo nhanh submodular sau nay. Paper khong xoay quanh mot approximation ratio cu the, ma dat ra ngon ngu rank function, polymatroid polyhedron, base polyhedron, va greedy linear optimization tren cac da dien nay. Gia tri lau dai cua paper la: no bien "submodularity" tu mot tinh chat to hop thanh mot doi tuong hinh hoc co the toi uu hoa va chung minh bang cong cu polyhedral.

## Classification Rationale

Paper duoc dat trong `submodular` vi no la goc structural cua set-submodularity. No giao thoa manh voi `matroid`, `polymatroid`, `polyhedral combinatorics`, va la tien de gian tiep cho minimization, greedy maximization, va cac mo rong nhu DR-submodularity.

## Setup

- Domain / model: mot ham set function `f : 2^E -> R` tren ground set huu han, kem cac polyhedron dang `x(S) <= f(S)`.
- Oracle / access model: paper mang tinh cau truc, khong o dang value-oracle approximation nhu cac paper sau nay.
- Assumptions: `f(emptyset) = 0`; tinh chat submodular la gia dinh trung tam de dac trung polymatroid / rank-like structures.

## Main Results

1. Paper dac trung hoa polymatroid bang rank-style set functions thoa dieu kien chuan hoa, don dieu, va submodular.
2. No mo ta cac dinh / extreme points cua polymatroid polyhedron thong qua cac chain thu duoc tu mot thu tu sap xep tren phan tu.
3. No chung minh linear optimization tren polymatroid co the giai bang greedy: sap xep trong so va cap phat increment theo cac sai khac `f(A_i) - f(A_{i-1})`.

## Core Algorithmic Idea

Y tuong cot loi la chuyen bai toan toi uu hoa tu "chon tap" sang "toi uu hoa tuyen tinh tren mot polyhedron". Khi da co thu tu giam dan cua trong so `c_1 >= ... >= c_n`, nghiem greedy duoc xay bang cach cho bien thu `i` nhan luong tang them bang do chenh giua rank tren prefix moi va prefix cu. Toan bo nghiem sinh ra tu mot chain tight-set, va dieu nay bien greedy thanh cong cu hinh hoc chinh xac chu khong chi la heuristic.

## Proof / Analysis Strategy

- Buoc 1: dinh nghia polyhedron / base polyhedron gan voi ham `f`, roi chi ra submodularity la dieu kien dung de cac bat dang thuc tap con "khoa" nhau mot cach dung.
- Buoc 2: xet mot thu tu phan tu do trong so gay ra, xay chain prefix `A_1 subset ... subset A_n`, va tao nghiem greedy tu cac sai khac rank tren chain nay.
- Buoc 3: chung minh moi nghiem toi uu tuyen tinh co the dua ve dang chain-tight; tu do suy ra dinh cua polyhedron va tinh dung cua greedy.

## Key Techniques

- polyhedral encoding cua submodularity
- chain-tight analysis cho extreme points
- greedy linear optimization tren polymatroid
- matroid rank / polymatroid rank correspondence

## Key Lemmas Or Structural Claims

- Dieu kien submodular + monotone + chuan hoa dac trung lop polymatroid rank functions.
- Cac dinh cua polymatroid co the bieu dien bang nghiem greedy sinh tu mot thu tu tren `E`.
- Mot ham tuyen tinh dat toi uu tren polymatroid tai mot nghiem chain-based, nen sap xep theo trong so la du.

## Delicate Points / Caveats

- Day la paper structural, khong nen doc voi ky vong tim mot approximation theorem theo kieu hien dai.
- Notation polyhedral trong paper co the khac ngon ngu `base polytope` / `Lovasz extension` ma literature sau nay dung.
- Greedy o day la greedy cho linear objective tren polymatroid, khong phai truc tiep greedy cho submodular maximization duoi rang buoc cardinality.

## Extraction To Concepts

- Dinh nghia / notation nen dua vao `concepts/`: polymatroid polyhedron, base polyhedron, chain-tight set, rank-function viewpoint.
- Lemma co the tai su dung: greedy toi uu hoa ham tuyen tinh tren polymatroid.
- Technique lap lai: bien bai toan to hop thanh bai toan polyhedral roi dung exchange / extreme-point reasoning.
- Quan he voi nhom khac: day la cay cau noi truc tiep sang SFM, matroid optimization, va ve sau la discrete convex analysis.

## Extraction To Syntheses

- Cap nhat `syntheses/submodular.md` nhu paper foundation so 1 cho polyhedral viewpoint.
- `syntheses/k-submodular.md` khong can them ket qua truc tiep, nhung nen nhac no la goc cua "structured diminishing returns on richer domains".
- `syntheses/dr-submodular.md` co the nhac toi nhu mot precedent cua viec ma hoa tinh chat submodular bang hinh hoc / regularity.
- `syntheses/mixed.md` nen them neu sau nay can mot note ve "transfer of proof ideas via polyhedral structure".

## Weaknesses / Limits

- Paper cu, notation day dac, va khong toi uu cho viec hoc nhanh neu chua quen polyhedral combinatorics.
- Khong cho ngay mot recipe algorithmic cho submodular maximization / minimization hien dai; gia tri cua no la ngon ngu va structure.

## Research Ideas Triggered

- Theo doi mot "polyhedral lineage" tu Edmonds sang Cunningham, Schrijver, Lovasz extension, va discrete convexity.
- Kiem tra xem trong cac bai toan k-submodular / DR-submodular hien dai, co doi tuong polyhedral nao dong vai tro giong polymatroid khong.