Home Bookmarks Papers Blog

Coresets for Discrete Integration and Clustering

Sariel Har-Peled.

Given a set P of n points on the real line and a(potentially infinite) family of functions, we investigate the problem of finding a small(weighted) subset \Coreset \subseteq P, such that for any f in \Family, we have that f(P) is a (1\pm µ)-approximation to f(\Coreset). Here, f(Q)=\sumq in Q w(q) f(q) denotes the weighted discrete integral of f over the point set Q, where w(q) is the weight assigned to the point q.

We study this problem, and provide tight bounds on the size \Coreset for several families of functions. As an application, we present some coreset constructions for clustering.

Postscript, PDF.
Talk: source.
Last modified: Wed Apr 11 09:28:40 CDT 2007