Book chapter
No Coreset, No Cry: II
FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, pp.107-115
Lecture Notes in Computer Science, Springer Berlin Heidelberg
2005
DOI: 10.1007/11590156_8
Abstract
Let P be a set of n points in d-dimensional Euclidean space, where each of the points has integer coordinates from the range [ − Δ, Δ], for some Δ ≥ 2. Let ε > 0 be a given parameter. We show that there is subset Q of P, whose size is polynomial in (log Δ)/ε, such that for any k slabs that cover Q, their ε-expansion covers P. In this result, k and d are assumed to be constants. The set Q can also be computed efficiently, in time that is roughly n times the bound on the size of Q. Besides yielding approximation algorithms that are linear in n and polynomial in log Δ for the k-slab cover problem, this result also yields small coresets and efficient algorithms for several other clustering problems.
Details
- Title: Subtitle
- No Coreset, No Cry: II
- Creators
- Michael Edwards - University of IowaKasturi Varadarajan - University of Iowa
- Resource Type
- Book chapter
- Publication Details
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, pp.107-115
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/11590156_8
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Language
- English
- Date published
- 2005
- Academic Unit
- Computer Science
- Record Identifier
- 9984259467602771
Metrics
4 Record Views