  


Computing Minimum Volume Enclosing AxisAligned Ellipsoids
Piyush Kumar (piyushacm.org) Abstract: Given a set of points $\cS = \{x^1,\ldots,x^m\} \subset \R^n$ and $\eps > 0$, we propose and analyze an algorithm for the problem of computing a $(1 + \eps)$approximation to the the minimum volume axisaligned ellipsoid enclosing $\cS$. We establish that our algorithm is polynomial for fixed $\eps$. In addition, the algorithm returns a small core set $\cX \subseteq \cS$, whose size is independent of the number of points $m$, with the property that the minimum volume axisaligned ellipsoid enclosing $\cX$ is a good approximation of the minimum volume axisaligned ellipsoid enclosing $\cS$. Our computational results indicate that the algorithm exhibits significantly better performance than that indicated by the theoretical worstcase complexity result. Keywords: Axisaligned ellipsoids, enclosing ellipsoids, core sets, approximation algorithms Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Category 2: Nonlinear Optimization Citation: Journal of Optimization Theory and Applications, 136 (2), pp. 211  228 (2008). Download: Entry Submitted: 06/28/2006 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  