A Note on Approximate Minimum Volume Enclosing Ellipsoid of Ellipsoids

We study the problem of computing the minimum volume enclosing ellipsoid (MVEE) containing a given set of ellipsoids S = {E₁, E₂, _hellip, E_n} sube Ropf^d. We show how to efficiently compute a small set X sube S of size at most a = |X| = O(d²/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(nd^omega + d³)) 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].