A Faster Cutting Plane Method and itsImplications for Combinatorial and Convex OptimizationYin Tat Lee
[email protected] Sidford
[email protected] Chiu-wai Wong
UC [email protected] this paper we improve upon the running time for finding a point in a convex set given
a separation oracle. In particular, given a separation oracle for a convex set K ⊂ Rn that is
contained in a box of radius R we show how to either compute a point in K or prove that K
does not contain
