Remarks on Coresets for Minimum Enclosing Ellipsoids
Presenter
December 9, 2011
Keywords:
- applied combinatorics
- integer programming
- convex programming
- volume estimation
- ellipsoidal hulls
MSC:
- 68W40
- 68W25
- 68Wxx
- 90C25
- 90C20
- 90C10
- 90Cxx
- 90-xx
Abstract
Let S be a set of n points in d dimensions. The Minimum Enclosing Ellipsoid MEE(S) is the unique ellipsoid of smallest volume that contains S. MEE(S) is determined by some subset C of S of at most d(d + 3)/2 points, called the contact points or support points. A coreset of S for MEE is a subset S' of S such that MEE(S') is roughly the same as MEE(S). There are (at least) two varieties of such approximation, with corresponding coresets; one variety has S a subset of (1+epsilon)MEE(S'), for epsilon>0, and the other variety is ellipsoid E such that E is a subset of MEE(S), which in turn is a subset of (1+epsilon)E. I will review these ideas, and slightly re-cast the existence proof for the second variety.