Opening The Ellipsoid Algorithm
The Ellipsoid Algorithm
- Length
- 31 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 4: Before the lecture
The ellipsoid algorithm solves linear programs in polynomial time, given only a separation oracle for a convex polytope. O'Donnell sketches it in Lecture 19a of CS Theory Toolkit, a graduate course at Carnegie Mellon University that assumes linear programming and asymptotic notation. He first reduces linear programming to robust emptiness testing, with the polytope inside a box of radius and containing a box of radius . The algorithm keeps an ellipsoid enclosing the feasible region and replaces it whenever its center violates a constraint. Each round cuts the volume by a factor of at least , so the running time is polynomial in the bit length of the constraints. The last part shows why convexity guarantees a separating hyperplane and how oracles handle exponentially many constraints.

Your comment is kept while you sign up.Sign in
Shrinks an enclosing ellipsoid by a factor of per round to test a polytope for emptiness in polynomial time.
The ellipsoid algorithm solves linear programs in polynomial time, given only a separation oracle for a convex polytope. O'Donnell sketches it in Lecture 19a of CS Theory Toolkit, a graduate course at Carnegie Mellon University that assumes linear programming and asymptotic notation. He first reduces linear programming to robust emptiness testing, with the polytope inside a box of radius and containing a box of radius . The algorithm keeps an ellipsoid enclosing the feasible region and replaces it whenever its center violates a constraint. Each round cuts the volume by a factor of at least , so the running time is polynomial in the bit length of the constraints. The last part shows why convexity guarantees a separating hyperplane and how oracles handle exponentially many constraints.
This lecture
Lecture 60 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.