Combinatorial Optimization

Linear programming, duality, and submodular optimization over discrete structures.

Polyhedra — x : Ax ≤ b — an intersection of half-spaces, with corners where constraints go tight.
Linear Programming — Maximize c^ x over a polytope; a finite optimum sits at a vertex.
Simplex Method — Add slacks, then pivot vertex to vertex — enter a profitable variable, leave by the ratio test — until the objective row turns non-positive.
LP Duality — Combine the constraints to bound the primal; the tightest such bound is the dual b^ y, and it meets the optimum.
Complementary Slackness — y^_i (b_i - a_i^ x^) = 0 — slack constraints have zero dual price; active variables force tight dual constraints.
Submodularity — Diminishing returns for set functions, and greedy's (1 - 1/e) guarantee.

Further Topics

Ford–Fulkerson / Augmenting Paths — Augmenting paths in the residual network give the maximum flow.
Bipartite Matching & Hall's Theorem — Saturate one side exactly when every set has enough neighbors.
Assignment Problem / Hungarian Algorithm — Min-cost perfect matching by row and column reduction.
Matroids & the Greedy Algorithm — The exchange axiom is exactly when greedy is optimal.
Integer Programming & LP Relaxation — Relax integrality for a bound, then measure the integrality gap.
Total Unimodularity — When every LP vertex is an integer point.
Branch & Bound — Bound each subproblem by its relaxation, then prune what cannot win.
The Traveling Salesman Problem — Metric TSP, the double-tree 2-approximation, and Christofides.
Knapsack & DP / FPTAS — Pseudo-polynomial profit DP, then profit rounding for a fully polynomial approximation scheme.
Approximation Algorithms & Ratio — Provable closeness to optimum: ratio, the matching bound, and the integrality gap.