# Ellipsoid method

### From Glossary

This algorithm seeks to solve by iterations that begin with and , where is a measure of the smallest datum that can be represented -- i.e., is a solution if, and only if, it satisfies . If the current iterate, , does not satisfy this, a new pair is defined by choosing one of the violated inequalities, say . Then, let , and apply the following rules:

By treating the objective as a constraint, say and/or , the ellipsoid method can be used to solve a linear program. Its significance is that it was the first algorithm for linear programming shown to have polynomial time complexity.