Videos

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.