Fetching the paper…

Reading the bibliography…

On the Sensitivity of Shape Fitting Problems · Around

2012

On the Sensitivity of Shape Fitting Problems

Varadarajan, Kasturi, Xiao, Xin

Original
PDF
Post on X

Understand

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.

Built on

k k -Means projective clustering
Pankaj K. Agarwal and Nabil H. Mustafa · 2004
Earlier work this paper cites.
On coresets for k k -means and k k -median clustering
Sariel Har-Peled and Soham Mazumdar · 2004
Earlier work this paper cites.
Subgradient and sampling algorithms for ℓ 1 \ell_{1} regression
Kenneth L. Clarkson · 2005
Earlier work this paper cites.
A PTAS for k k -means clustering based on weak coresets
Dan Feldman, Morteza Monemizadeh, and Christian Sohler · 2007
Earlier work this paper cites.

Similar

Twice-Ramanujan sparsifiers
Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava · 2009
Cited alongside, same era.
On coresets for k k -median and k k -means clustering in metric and euclidean spaces and their applications
Ke Chen · 2009
Cited alongside, same era.
Sampling algorithms and coresets for ℓ p \ell_{p} regression
Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, and Michael W. Mahoney · 2009
Cited alongside, same era.
CUR matrix decompositions for improved data analysis
Michael W. Mahoney and Petros Drineas · 2009
Cited alongside, same era.

Then

Universal ϵ \epsilon -approximators for integrals
Michael Langberg and Leonard J. Schulman · 2010
Later among the works it cites.
A unified framework for approximating and clustering data
Original
Dan Feldman and Michael Langberg · 2011
Later among the works it cites.
Data reduction for weighted and outlier-resistant clustering
Dan Feldman and Leonard J. Schulman · 2012
Closest in time.
A near-linear algorithm for projective clustering integer points
Kasturi Varadarajan and Xin Xiao · 2012
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…