Computer Science – Learning
Scientific paper
2011-07-12
Computer Science
Learning
10 pages
Scientific paper
This paper considers the model introduced by Bilu and Linial (2010), who study problems for which the optimal clustering does not change when the distances are perturbed by multiplicative factors. They show that even when a problem is NP-hard, it is sometimes possible to obtain polynomial-time algorithms for instances resilient to large perturbations, e.g. on the order of $O(\sqrt{n})$ for max-cut clustering. Awasthi et al. (2010) extend this line of work by considering center-based objectives, and Balcan and Liang (2011) consider the $k$-median and min-sum objectives, giving efficient algorithms for instances resilient to certain constant multiplicative perturbations. Here, we are motivated by the question of to what extent these assumptions can be relaxed while allowing for efficient algorithms. We show there is little room to improve these results by giving NP-hardness lower bounds for both the $k$-median and min-sum objectives. On the other hand, we show that multiplicative resilience parameters, even only on the order of $\Theta(1)$, can be so strong as to make the clustering problem trivial, and we exploit these assumptions to present a simple one pass streaming algorithm for the $k$-median objective. We also consider a model of additive perturbations and give a correspondence between additive and multiplicative notions of stability. Our results provide a close examination of the consequences of assuming, even constant, stability in data.
No associations
LandOfFree
Data Stability in Clustering: A Closer Look does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Data Stability in Clustering: A Closer Look, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data Stability in Clustering: A Closer Look will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-566166