A Note on Approximate Minimum Volume Enclosing Ellipsoid of Ellipsoids
Sachin Jambawalikar, Piyush Kumar · 2008
We study the problem of computing the minimum volume enclosing ellipsoid (MVEE) containing a given set of ellipsoids S = {E1, E2,hellip, En} sube Ropfd. We show how to efficiently compute a small set X sube S of size at most a = |X| = O(d2/epsi ) whose minimum volume ellipsoid is an (1 + epsi)-approximation to the minimum volume ellipsoid of S. We use an augmented real num ber model of computation to achieve a running time of O(alpha(ndomega+ d3)) where omega < 2.376 is the exponent of square matrix multiplication. This is the best known complexity for solving the MVEE problem when n Gt d and e is large. The algorithm is built on the previous work by Kumar and Yrfdirim [17].