CSDM: Nearly Optimal Deterministic Algorithms Via M-Ellipsoids

Nearly Optimal Deterministic Algorithms Via M-Ellipsoids - Santosh Vempala

Santosh Vempala
Georgia Institute of Technology
January 30, 2011
Milman's ellipsoids play an important role in modern convex geometry. Here we show that their proofs of existence can be turned into efficient algorithms, and these in turn lead to improved deterministic algorithms for volume estimation of convex bodies, finding the shortest lattice vector under general norms and integer programming.