The Ellipsoid Method (Shor 1970, Khachian 1979) was the first polynomial-time algorithm for linear programming — a landmark theoretical result. It maintains an ellipsoid guaranteed to contain the feasible region and iteratively shrinks it by cutting through the center with the most-violated constraint halfspace, producing a new smaller ellipsoid. Each step reduces volume by factor e^(-1/(2n)), giving O(n²) iterations to ε-precision. Though impractical for dense LP (worse than simplex in practice), it proved LP is in P and generalizes to convex optimization via separation oracles, powering combinatorial algorithms like the Lovász theta function.