TY - GEN

T1 - Coresets for discrete integration and clustering

AU - Har-Peled, Sariel

N1 - Funding Information:
★ The latest version of this paper is avaiable online [1]. ★★Work on this paper was partially supported by a NSF 0132901.
Funding Information:
The latest version of this paper is avaiable online [1]. Work on this paper was partially supported by a NSF CAREER award CCR-0132901.

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 -