quality:corruption
Theoretical importance

The ellipsoid method is an important theoretical technique in combinatorial optimization. In computational complexity theory, the ellipsoid algorithm is attractive because its complexity depends on the number of columns and the digital size of the coefficients, but not on the number of rows.

The ellipsoid method can be used to show that many algorithmic problems on convex sets are polynomial-time equivalent.