Lecture slides by Kevin Wayne
Last updated on 7/25/17 11:09 AM
LINEAR PROGRAMMING III
‣
ellipsoid algorithm
‣
combinatorial optimization
‣
matrix games
‣
open problems
LINEAR PROGRAMMING III
‣
ellipsoid algorithm
‣
combinatorial optimization
‣
matrix games
‣
open problems
Lecture notes on the ellipsoid algorithm by Michel X. Goemans!
http://math.mit.edu/~goemans/18433S07/ellipsoid.pdf
Geometric divide-and-conquer
To find a point in P:
3
P
Geometric divide-and-conquer
To find a point in P:
・
Maintain ellipsoid E containing P.
4
E
P