2026-08-14T17:12:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3883 2024-03-06T10:34:35Z ddc:004 open_access

On the Sensitivity of Shape Fitting Problems Varadarajan, Kasturi Xiao, Xin Coresets shape fitting k-means subspace approximation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kasturi Varadarajan and Xin Xiao 2012 Is Part Of LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2012.486 urn:nbn:de:0030-drops-38830 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.486 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode