Coresets for discrete integration and clustering

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationFSTTCS 2006
Subtitle of host publicationFoundations of Software Technology and Theoretical Computer Science - 26th International Conference, Proceedings
Editors[initials] N. Arun-Kumar
PublisherSpringer
Pages33-44
Number of pages12
ISBN (Print)9783540499947
DOIs
StatePublished - 2006
Event26th International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2006 - Kolkata, India
Duration: Dec 13 2006Dec 15 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4337 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other26th International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2006
Country/TerritoryIndia
CityKolkata
Period12/13/0612/15/06

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Coresets for discrete integration and clustering'. Together they form a unique fingerprint.

Cite this