Ellipsoid Method

Abstract

In this article, we give an overview of the Ellipsoid Method. We start with a historic introduction and provide a basic algorithm in section “Method”. Techniques to avoid two important assumptions required by this algorithm are considered in section “Polynomially Running Time: Avoiding the Assumptions”. After the discussion of some implementation aspects, we are able to show the polynomial running time of the Ellipsoid Method. The second section is closed with some modifications in order to speed up the running time of the ellipsoid algorithm. In section “Applications”, we discuss some theoretical implications of the Ellipsoid Method to linear programming and combinatorial optimization.