TY - GEN
T1 - Coresets for discrete integration and clustering
AU - Har-Peled, Sariel
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2006.
PY - 2006
Y1 - 2006
N2 - 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 S ⊆ P, such that for any f ∈ F, we have that f(P) is a (1±ε)-approximation to f(S). Here, f(Q) = ∑q∈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 S for several families of functions. As an application, we present some coreset constructions for clustering.
AB - 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 S ⊆ P, such that for any f ∈ F, we have that f(P) is a (1±ε)-approximation to f(S). Here, f(Q) = ∑q∈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 S for several families of functions. As an application, we present some coreset constructions for clustering.
UR - http://www.scopus.com/inward/record.url?scp=84871957086&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84871957086&partnerID=8YFLogxK
U2 - 10.1007/11944836_6
DO - 10.1007/11944836_6
M3 - Conference contribution
AN - SCOPUS:84871957086
SN - 9783540499947
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 33
EP - 44
BT - FSTTCS 2006
A2 - Arun-Kumar, [initials] N.
PB - Springer
T2 - 26th International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2006
Y2 - 13 December 2006 through 15 December 2006
ER -