Conference proceeding
On the Sensitivity of Shape Fitting Problems
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012), Vol.18, pp.486-497
12/14/2012
DOI: 10.4230/LIPIcs.FSTTCS.2012.486
Abstract
In this article, we study shape fitting problems, epsilon-coresets, and total sensitivity. We focus on the (j,k)-projective clustering problems, including k-median/k-means, k-line clustering, j-subspace approximation, and the integer (j,k)-projective clustering problem. We derive upper bounds of total sensitivities for these problems, and obtain epsilon-coresets using these upper bounds. Using a dimension-reduction type argument, we are able to greatly simplify earlier results on total sensitivity for the k-median/k-means clustering problems, and obtain positively-weighted epsilon-coresets for several variants of the (j,k)-projective clustering problem. We also extend an earlier result on epsilon-coresets for the integer (j,k)-projective clustering problem in fixed dimension to the case of high dimension.
Details
- Title: Subtitle
- On the Sensitivity of Shape Fitting Problems
- Creators
- Kasturi VaradarajanXin Xiao
- Resource Type
- Conference proceeding
- Publication Details
- IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012), Vol.18, pp.486-497
- DOI
- 10.4230/LIPIcs.FSTTCS.2012.486
- ISSN
- 1868-8969
- Publisher
- Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik; Dagstuhl, Germany
- Comment
- Leibniz International Proceedings in Informatics (LIPIcs)
- Language
- English
- Date published
- 12/14/2012
- Academic Unit
- Computer Science
- Record Identifier
- 9984259500802771
Metrics
8 Record Views