Clarkson's Algorithm for Linear Programming
Clarkson's randomized algorithm reduces solving an n×d LP to O(d log(n/d)) sub-problems of size O(d²)×d by reweighting violated constraints — a multiplicative-weights argument in the geometry of basic feasible solutions.
13 minute
linear-programming
randomized-algorithms
optimization
combinatorics