Approximate Minimum Volume Enclosing Ellipsoids Using Core Sets
Piyush Kumar, E. Alper Yıldırım · 2003
We study the problem of computing the minimum volume enclosing ellipsoid containing a given point set S = {p1, p2, . . . , pn} ⊆ R. Using “core sets” and a column generation approach, we develop a (1 + )-approximation algorithm. We prove the existence of a core set X ⊆ S of size at most |X| = α = O ( d ( log d + 1 )) . We describe an algorithm that computes the set X and a (1 + )-approximation to the minimum volume enclosing ellipsoid of S in O(ndα+ α log α ) operations by using Khachiyan’s algorithm to solve each subproblem. This result is an improvement over the previously known algorithms especially for input sets with n d and reasonably small values of . We also discuss extensions to the cases in which the input set consists of balls or ellipsoids.