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_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.
@cite_20: In recent years, the capacitated center problems have attracted a lot of research interest. Given a set of vertices V, we want to find a subset of vertices S, called centers, such that the maximum cluster radius is minimized. Moreover, each center in S should satisfy some capacity constraint, which could be an upper or lower bound on the number of vertices it can serve. Capacitated k-center problems with one-sided bounds (upper or lower) have been well studied in previous work, and a constant factor approximation was obtained.
In this paper, we answer their question in the affirmative. Specifically, we provide a novel method to complete step ( 2 ) in linear time. For @math -BCenter, we apply a spatial partition idea to build a system of linear equations and inequalities that has the size independent of @math , and round the feasible solution to be an integral solution (i.e., a feasible partition on @math ) efficiently without increasing the objective value. Comparing with the existing method for @math -BCenter @cite_20 , we improve the approximation ratio from @math to @math and significantly reduce the running time by avoiding to solve the large-scale matching problem. To solve @math -BMedian and @math -BMeans, we generalize the spatial partition idea and replace the system of linear equations and inequalities by a model of linear programming. More importantly, a feasible partition on @math can be efficiently obtained as well. We adopt the results from @cite_28 @cite_15 and obtain the same constant factor and @math -approximations, while our running times are much lower.