The problem of constrained clustering has attracted significant attention in the past decades. In this paper, we study the balanced @math -center, @math -median, and @math -means clustering problems where the size of each cluster is constrained by the given lower and upper bounds. The problems are motivated by the applications in processing large-scale data in high dimension. Existing methods often need to compute complicated matchings (or min cost flows) to satisfy the balance constraint, and thus suffer from high complexities especially in high dimension. We develop an effective framework for the three balanced clustering problems to address this issue, and our method is based on a novel spatial partition idea in geometry. For the balanced @math -center clustering, we provide a @math -approximation algorithm that improves the existing approximation factors; for the balanced @math -median and @math -means clusterings, our algorithms yield constant and @math -approximation factors with any @math . More importantly, our algorithms achieve linear or nearly linear running times when @math is a constant, and significantly improve the existing ones. Our results can be easily extended to metric balanced clusterings and the running times are sub-linear in terms of the complexity of @math -point metric.
@cite_28: 
@cite_38: In distributed machine learning, data is dispatched to multiple machines for processing. Motivated by the fact that similar data points are often belonging to the same or similar classes, and more generally, classification rules of high accuracy tend to be "locally simple but globally complex", we propose data dependent dispatching that takes advantage of such structures. Our main technical contribution is to provide algorithms with provable guarantees for data-dependent dispatching, that partition the data in a way that satisfies important conditions for accurate distributed learning, including fault tolerance and balancedness. We show the effectiveness of our method over the widely used random partitioning scheme in several real world image and advertising datasets.
@cite_15: The classical center based clustering problems such as k-means 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 r -gather 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 k-means 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 k-centers c 1, ..., c k such that the objective function ( _ i = 1 ^ k _ x 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 e > 0, let l denote the size of the smallest list of k-centers such that at least one of the k-centers gives a (1 + e) 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 ) ) k-centers. We also give a closely matching lower bound of (2^ (k ) ). Moreover, our algorithm runs in time (O (n d 2^ O (k ) ) ). This is a significant improvement over the previous result of Ding and Xu (2015) who gave an algorithm with running time O(n d ⋅ (log n) k ⋅ 2 p o l y(k e)) and output a list of size O((log n) k ⋅ 2 p o l y(k e)). Our techniques generalize for the k-median problem and for many other settings where non-Euclidean distance measures are involved.
Clustering problems commonly involve two key steps: ). determine the @math cluster centers and ). partition the input data into @math clusters. For ordinary clustering problems, step ( 2 ) is trivial. Namely, we just need to assign each data point to its nearest cluster center to minimize the total clustering cost. However, step ( 2 ) can be complicated for constrained clustering problems. In general, we need to compute the matching between input points @math and the obtained cluster centers, such that the objective value is minimized and the constraint (e.g., the balancedness) can be satisfied simultaneously. For example, the algorithms in @cite_38 @cite_28 @cite_15 all need to reduce it to be a max flow or min cost flow problem. They build a bipartite graph between @math and the @math cluster centers, and the numbers of the vertices @math and edges @math are both linear on @math ; therefore, their running times will be @math that is at least quadratic on the input size. The authors of @cite_28 proposed the open problem: can we avoid computing the high complexity matching in step ( 2 )?