An Oblivious Ellipsoid Algorithm for Solving a System of (In)Feasible Linear Inequalities

Jourdain Lamperski, Robert M. Freund, Michael J. Todd

The ellipsoid algorithm is a fundamental algorithm for computing a solution to the system of $m$ linear inequalities in $n$ variables $(P):A^{\top }x\le u$ when its set of solutio…