The ellipsoid method is an algorithm for solving linear programs. It works by first reducing the problem of optimization to a problem of feasibility. To check whether the resulting polytope is empty, it is bounded by an ellipsoid. Then, in successive steps, the ellipsoid is reduced in size until the center of the ellipsoid is in the polytope, or until the ellipsoid is too small. In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear. ...

When it was invented by M. Grötschel, L. Lovász and A. Schrijver in 1981, the ellipsoid method was the first algorithm for solving linear program whose runtime was provably polynomial. In practice however, variations of the simplex algorithm are much faster. Karmarkar's algorithm (1984) solves the linear program in provably polynomial time, and is much faster than the ellipsoid method in both theory and practice. In mathematical optimization theory, the simplex algorithm of George Dantzig is the fundamental technique for numerical solution of the linear programming problem. ... In mathematics, Karmarkars algorithm is an algorithm for solving linear programming problems. ...