Abstract
The classical center based clustering problems such as kmeans/median/center assume that the optimal clusters satisfy the locality property that the points in the same cluster are close to each other. A number of clustering problems arise in machine learning where the optimal clusters do not follow such a locality property. For instance, consider the rgather clustering problem where there is an additional constraint that each of the clusters should have at least r points or the capacitated clustering problem where there is an upper bound on the cluster sizes. Consider a variant of the kmeans problem that may be regarded as a general version of such problems. Here, the optimal clusters O_1, ..., O_k are an arbitrary partition of the dataset and the goal is to output kcenters c_1, ..., c_k such that the objective function sum_{i=1}^{k} sum_{x in O_{i}} x  c_{i}^2 is minimized. It is not difficult to argue that any algorithm (without knowing the optimal clusters) that outputs a single set of k centers, will not behave well as far as optimizing the above objective function is concerned. However, this does not rule out the existence of algorithms that output a list of such k centers such that at least one of these k centers behaves well. Given an error parameter epsilon > 0, let l denote the size of the smallest list of kcenters such that at least one of the kcenters gives a (1+epsilon) approximation w.r.t. the objective function above. In this paper, we show an upper bound on l by giving a randomized algorithm that outputs a list of 2^{~O(k/epsilon)} kcenters. We also give a closely matching lower bound of 2^{~Omega(k/sqrt{epsilon})}. Moreover, our algorithm runs in time O(n * d * 2^{~O(k/epsilon)}). This is a significant improvement over the previous result of Ding and Xu who gave an algorithm with running time O(n * d * (log{n})^{k} * 2^{poly(k/epsilon)}) and output a list of size O((log{n})^k * 2^{poly(k/epsilon)}). Our techniques generalize for the kmedian problem and for many other settings where nonEuclidean distance measures are involved.
BibTeX  Entry
@InProceedings{bhattacharya_et_al:LIPIcs:2016:5717,
author = {Anup Bhattacharya and Ragesh Jaiswal and Amit Kumar},
title = {{Faster Algorithms for the Constrained kMeans Problem}},
booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
pages = {16:116:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770019},
ISSN = {18688969},
year = {2016},
volume = {47},
editor = {Nicolas Ollinger and Heribert Vollmer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5717},
URN = {urn:nbn:de:0030drops57179},
doi = {10.4230/LIPIcs.STACS.2016.16},
annote = {Keywords: kmeans, kmedian, approximation algorithm, sampling}
}
Keywords: 

kmeans, kmedian, approximation algorithm, sampling 
Seminar: 

33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) 
Issue Date: 

2016 
Date of publication: 

16.02.2016 