Title: Efficient Algorithms for Large-Scale Geometric Optimization Problems and Core Sets

Given n points in d dimensions and ε ∈ (0,1), we propose algorithms to compute a (1+ε)-volume approximation for the minimum enclosing ball (MEB) and the minimum enclosing ellipsoid (MEE) problems. We focus on instances with very large number of points n and moderately high dimensions d.
     For the MEB problem, we propose a column generation algorithm that exploits the underlying structure. We establish new complexity results by finding upper bounds on the number of columns generated. To obtain a (1+ε)-volume approximation to the optimal solution, our algorithm requires the generation of at most Ο(d/ε) columns for the MEB problem. This result implies that one can efficiently compute a subset (core set) of n points of size Ο(d/ε) that provides a good representation of the input set. We present extensive computational results.
     For the MVEE problem, we propose a modification of Khachiyan's first-order algorithm and obtain a slightly improved complexity result of Ο(nd³/ε). As a byproduct, our analysis reveals that a core set of size at most Ο(d²/ε) can be efficiently computed.
     Since both of our core set results are independent of the number of points n, our results imply that fairly large instances of both of these geometric optimization problems can be efficiently solved since they admit "small" core sets that can be computed in practice.
     This is joint work with Joseph S. B. Mitchell and Piyush Kumar at Stony Brook University.
Short Bio: Emre Alper Yildirim earned his Ph.D. from Cornell University in 2001 under the supervision of Prof. Michael J. Todd. His dissertation presented a new perspective on sensitivity analysis in linear and semidefinite programming based entirely on interior-point methods. He joined the Department of Applied Mathematics and Statistics at Stony Brook University as an Assistant Professor in the fall of 2001. His research interests are centered around the theory, algorithms, and applications of convex optimization. Dr. Yildirim's research is partly funded by a Faculty Early CAREER Development Award by the National Science Foundation.