text: In this paper, we consider a class of constrained clustering problems of points in @math , where @math could be rather high. A common feature of these problems is that their optimal clusterings no longer have the locality property (due to the additional constraints), which is a key property required by many algorithms for their unconstrained counterparts. To overcome the difficulty caused by the loss of locality, we present in this paper a unified framework, called Peeling-and-Enclosing (PnE) , to iteratively solve two variants of the constrained clustering problems, constrained @math -means clustering ( @math -CMeans) and constrained @math -median clustering ( @math -CMedian). Our framework is based on two standalone geometric techniques, called Simplex Lemma and Weaker Simplex Lemma , for @math -CMeans and @math -CMedian, respectively. The simplex lemma (or weaker simplex lemma) enables us to efficiently approximate the mean (or median) point of an unknown set of points by searching a small-size grid, independent of the dimensionality of the space, in a simplex (or the surrounding region of a simplex), and thus can be used to handle high dimensional data. If @math and @math are fixed numbers, our framework generates, in nearly linear time ( i.e., @math ), @math @math -tuple candidates for the @math mean or median points, and one of them induces a @math -approximation for @math -CMeans or @math -CMedian, where @math is the number of points. Combining this unified framework with a problem-specific selection algorithm (which determines the best @math -tuple candidate), we obtain a @math -approximation for each of the constrained clustering problems. We expect that our technique will be applicable to other constrained clustering problems without locality.
  @cite_45: The Euclidean @math -means problem is a classical problem that has been extensively studied in the theoretical computer science, machine learning and the computational geometry communities. In this problem, we are given a set of @math points in Euclidean space @math , and the goal is to choose @math centers in @math so that the sum of squared distances of each point to its nearest center is minimized. The best approximation algorithms for this problem include a polynomial time constant factor approximation for general @math and a @math -approximation which runs in time @math . At the other extreme, the only known computational complexity result for this problem is NP-hardness [ADHP'09]. The main difficulty in obtaining hardness results stems from the Euclidean nature of the problem, and the fact that any point in @math can be a potential center. This gap in understanding left open the intriguing possibility that the problem might admit a PTAS for all @math . In this paper we provide the first hardness of approximation for the Euclidean @math -means problem. Concretely, we show that there exists a constant @math such that it is NP-hard to approximate the @math -means objective to within a factor of @math . We show this via an efficient reduction from the vertex cover problem on triangle-free graphs: given a triangle-free graph, the goal is to choose the fewest number of vertices which are incident on all the edges. Additionally, we give a proof that the current best hardness results for vertex cover can be carried over to triangle-free graphs. To show this we transform @math , a known hard vertex cover instance, by taking a graph product with a suitably chosen graph @math , and showing that the size of the (normalized) maximum independent set is almost exactly preserved in the product graph using a spectral analysis, which might be of independent interest.
  @cite_3: We show that k-means clustering is an NP-hard optimization problem, even if k is fixed to 2.
  @cite_16: 
summary: As for the hardness of the problem, Dasgupta @cite_3 showed that it is NP-hard for @math -means clustering in high dimensional space even if @math ; @cite_45 proved that there is no PTAS for @math -means clustering if both @math and @math are large, unless @math . Guruswami and Indyk @cite_16 showed that it is NP-hard to obtain any PTAS for @math -median clustering if @math is not a constant and @math is @math .