Approximate Clustering with Same-Cluster Queries
Nir Ailon1 , Anup Bhattacharya2 , Ragesh Jaiswal2 , and Amit Kumar2

arXiv:1704.01862v3 [] 4 Oct 2017

2

1
Technion, Haifa, Israel.⋆
Department of Computer Science and Engineering,
Indian Institute of Technology Delhi.⋆⋆

Abstract. Ashtiani et al. proposed a Semi-Supervised Active Clustering framework (SSAC), where
the learner is allowed to make adaptive queries to a domain expert. The queries are of the kind “do two
given points belong to the same optimal cluster?”, and the answers to these queries are assumed to be
consistent with a unique optimal solution. There are many clustering contexts where such same cluster
queries are feasible. Ashtiani et al. exhibited the power of such queries by showing that any instance of
the k-means clustering problem, with additional margin assumption, can be solved efficiently if one is
allowed O(k2 log k + k log n) same-cluster queries. This is interesting since the k-means problem, even
with the margin assumption, is NP-hard.
In this paper, we extend the work of Ashtiani et al. to the approximation setting showing that a few
of such same-cluster queries enables one to get a polynomial-time (1 + ε)-approximation algorithm for
the k-means problem without any margin assumption on the input dataset. Again, this is interesting
since the k-means problem is NP-hard to approximate within a factor (1 + c) for a fixed constant
0 < c < 1. The number of same-cluster queries used is poly(k/ε) which is independent of the size n
of the dataset. Our algorithm is based on the D2 -sampling technique, also known as the k-means++
seeding algorithm. We also give a conditional lower bound on the number of same-cluster queries
showing that if the Exponential
Time Hypothesis (ETH) holds, then any such efficient query algorithm

needs to make Ω polyklog k same-cluster queries. Our algorithm can be extended for the case when
the oracle is faulty, that is, it gives wrong answers to queries with some bounded probability. Another
result we show with respect to the k-means++ seeding algorithm is that a small modification to the kmeans++ seeding algorithm within the SSAC framework converts it to a constant factor approximation
algorithm instead of the well known O(log k)-approximation algorithm.

1

Introduction

Clustering is extensively used in data mining and is typically the first task performed when trying to understand large data. Clustering basically involves partitioning given data into groups or
clusters such that data points within the same cluster are similar as per some similarity measure.
Clustering is usually performed in an unsupervised setting where data points do not have any labels associated with them. The partitioning is done using some measure of similarity/dissimilarity
between data elements. In this work, we extend the work of Ashtiani et al. [AKBD16] who explored
the possibility of performing clustering in a semi-supervised active learning setting for center based
clustering problems such as k-median/means. In this setting, which they call Semi-Supervised Active Clustering framework or SSAC in short, the clustering algorithm is allowed to make adaptive
queries of the form:
do two points from the dataset belong to the same optimal cluster?.
where query answers are assumed to be consistent with a unique optimal solution. Ashtiani et
al. [AKBD16] started the study of understanding the strength of this model. Do hard clustering
problems become easy in this model? They explore such questions in the context of center-based
clustering problems. Center based clustering problems such as k-means are extensively used to
analyze large data clustering problems. Let us define the k-means problem in the Euclidean setting.
⋆
⋆⋆

Email address: nailon@cs.technion.ac.il
Email addresses: {anupb, rjaiswal, amitk}@cse.iitd.ac.in

Definition 1 (k-means problem). Given a dataset X ⊆ Rd containing n points, and a positive
integer k, find a set of k points C ⊆ Rd (called centers) such that the following cost function is
minimized:
X
Φ(C, X) =
min D(x, c).
x∈X

c∈C

D(x, c) denotes the squared Euclidean distance between c and x. That is, D(x, c) = ||x − c||2 .
Note that the k optimal centers c1 , ..., ck of the k-means problem define k clusters of points in
a natural manner. All points for which the closest center is ci belong to the ith cluster. This is
also known as the Voronoi partitioning and the clusters obtained in this manner using the optimal
k centers are called the optimal clusters. Note that the optimal center for the
1-means problem
P
def.

for any dataset X ⊆ Rd is the centroid of the dataset denoted by µ(X) =

x∈X

|X|

x

. This means

that if X1 , ...., Xk are the optimal clusters for the k-means problem on any dataset X ⊆ Rd and
c1 , ..., ck are the corresponding optimal centers, then ∀i, ci = µ(Xi ). The k-means problem has been
widely studied and various facts are known about this problem. The problem is tractable when
either the number k of clusters or the dimension d equal to 1. However, when k > 1 or d > 1, then
the problem is known to be NP-hard [Das08, Vat09, MNV12]. There has been a number of works
of beyond the worst-case flavour for k-means problem in which it is typically assumed that the
dataset satisfies some separation condition, and then the question is whether this assumption can
be exploited to design algorithms providing better guarantees for the problem. Such questions have
led to different definitions of separation and also some interesting results for datasets that satisfy
these separation conditions (e.g., [ORSS13, BBG09, ABS12]). Ashtiani et al. [AKBD16] explored
one such separation notion that they call the γ-margin property.
Definition 2 (γ-margin property). Let γ > 1 be a real number. Let X ⊆ Rd be any dataset and
k be any positive integer. Let PX = {X1 , ..., Xk } denote k optimal clusters for the k-means problem.
Then this optimal partition of the dataset PX is said to satisfy the γ-margin property iff for all
i 6= j ∈ {1, ..., k} and x ∈ Xi and y ∈ Xj , we have:
γ · ||x − µ(Xi )||< ||y − µ(Xi )||.
Qualitatively, what this means is that every point within some cluster is closer to its own cluster
center than a point that does not belong to this cluster. This seems to be a very strong separation
property. Ashtiani et al. [AKBD16] showed that the k-means clustering problem
is NP-hard even
√
when restricted to instances that satisfy the γ-margin property for γ = 3.4 ≈ 1.84. Here is the
formal statement of their hardness result.
Theorem 1 (Theorem 10 in [AKBD16]). Finding an optimal solution to k-means objective
function is NP-hard when k = Θ(nε ) for any
√ ε ∈ (0, 1), even when there is an optimal clustering
that satisfies the γ-margin property for γ = 3.4.
In the context of the k-means problem, the same-cluster queries within the SSAC framework are
decision questions of the form: Are points x, y such that x 6= y belong to the same optimal cluster?
3 Following is the main question explored by Ashitiani et al. [AKBD16]:
√
Under the γ-margin assumption, for a fixed γ ∈ (1, 3.4], how many queries must be made
in the SSAC framework for k-means to become tractable?
3

In case where the optimal solution is not unique, the same-cluster query answers are consistent with respect to
any fixed optimal clustering.

Ashtiani et al. [AKBD16] addressed the above question and gave a query algorithm. Their
algorithm, in fact, works for a more general setting where the clusters are not necessarily optimal.
In the more general setting, there is a target clustering X̄ = X̄1 , ..., X̄k of the given dataset X ⊆ Rd
(not necessarily optimal clusters) such that these clusters satisfy the γ-margin property (i.e., for
all i, x ∈ X̄i , and y ∈
/ X̄i , γ · ||x − µ(X̄i )||< ||y − µ(X̄i )||) and the goal of the query algorithm is to
output the clustering X̄. Here is the main result of Ashtiani et al.
Theorem 2 (Theorems 7 and 8 in [AKBD16]). Let δ ∈ (0, 1) and γ > 1. Let X ⊆ Rd
be any dataset containing n points, k be a positive integer, and X1 , ..., Xk be any target clustering
 of X that satisfies the γ-margin property. Then there is a query algorithm A that makes
k+log 1/δ
O k log n + k2 log(γ−1)
same-cluster queries and with probability at least (1 − δ) outputs the
4


k+log 1/δ
clustering X1 , ..., Xk . The running time of algorithm A is O kn log n + k2 log(γ−1)
.
4
The above result is a witness to the power of the SSAC framework. We extend this line of
work by examining the power of same-cluster queries in the approximation algorithms domain. Our
results do not assume any separation condition on the dataset (such as γ-margin as in [AKBD16])
and they hold for any dataset.
Since the k-means problem is NP-hard, an important line of research work has been to obtain
approximation algorithms for the problem. There are various efficient approximation algorithms
for the k-means problem, the current best approximation guarantee being 6.357 by Ahmadian et
al. [ANFSW16]. A simple approximation algorithm that gives an O(log k) approximation guarantee is the k-means++ seeding algorithm (also known as D 2 -sampling algorithm) by Arthur and
Vassilvitskii [AV07]. This algorithm is commonly used in solving the k-means problem in practice.
As far as approximation schemes or in other words (1 + ε)-approximation algorithms (for arbitrary
small ε < 1) are concerned, the following is known: It was shown by Awasthi et al. [ACKS15]
that there is some fixed constant 0 < c < 1 such that there cannot exist an efficient (1 + c) factor approximation unless P = NP. This result was improved by Lee et al. [LSW17] where it was
shown that it is NP-hard to approximate the k-means problem within a factor of 1.0013. However,
when either k or d is a fixed constant, then there are Polynomial Time Approximation Schemes
(PTAS) for the k-means problem.4 Addad et al. [CAKM16] and Friggstad et al. [FRS16] gave a
PTAS for the k-means problem in constant dimension. For fixed constant k, various PTASs are
known [KSS10, FMS07, JKS14, JKY15]. Following is the main question that we explore in this
work:
For arbitrary small ε > 0, how many same-cluster queries must be made in an efficient
(1 + ε)-approximation algorithm for k-means in the SACC framework? The running time
should be polynomial in all input parameters such as n, k, d and also in 1/ε.
Note that this is a natural extension of the main question explored by Ashtiani et al. [AKBD16].
Moreover, we have removed the separation assumption on the data. We provide an algorithm that
makes poly(k/ε) same-cluster queries and runs in time O(nd · poly(k/ε)). More specifically, here is
the formal statement of our main result:
Theorem 3 (Main result: query algorithm). Let 0 < ε ≤ 1/2, k be any positive integer, and
X ⊆ Rd . Then there is a query algorithm A that runs in time O(ndk 9 /ε4 ) and with probability at
least 0.99 outputs a center set C such that Φ(C, X) ≤ (1 + ε) · ∆k (X). Moreover, the number of
4

This basically means an algorithm that runs in time polynomial in the input parameters but may run in time
exponential in 1/ε.

same-cluster queries used by A is O(k9 /ε4 ). Here ∆k (X) denotes the optimal value of the k-means
objective function.
Note that unlike Theorem 2, our bound on the number of same-cluster queries is independent of
the size of the dataset. We find this interesting and the next natural question we ask is whether this
bound on the number of same-cluster queries is tight in some sense. In other words, does there exist
a query algorithm in the SSAC setting that gives (1+ε)-approximation in time polynomial in n, k, d
and makes significantly fewer queries than the one given in the theorem above? We answer this
question in the negative by establishing a conditional lower bound on the number of same-cluster
queries under the assumption that ETH (Exponential Time Hypothesis) [IP01, IPZ01] holds. The
formal statement of our result is given below.
Theorem 4 (Main result: query lower bound). If the Exponential Time Hypothesis (ETH)
holds, then there exists a constant c > 1 such that any c-approximation query algorithm for the
k
queries.
k-means problem that runs in time poly(n, d, k) makes at least
poly log k
Faulty query setting The existence of a same-cluster oracle that answers such queries perfectly may
be too strong an assumption. A more reasonable assumption is the existence of a faulty oracle that
can answer incorrectly but only with bounded probability. Our query approximation algorithm can
be extended to the setting where answers to the same-cluster queries are faulty. More specifically, we
can get wrong answers to queries independently but with probability at most some constant q < 1/2.
Also note that in our model the answer for a same-cluster query does not change with repetition.
This means that one cannot ask the same query multiple times and amplify the probability of
correctness. We obtain (1 + ε)-approximation guarantee for the k-means clustering problem in this
setting. The main result is given as follows.
Theorem 5. Let 0 < ε ≤ 1/2, k be any positive integer, and X ⊆ Rd . Consider a faulty SSAC
setting where the response to every same-cluster query is incorrect with probability at most some
constant q < 1/2. In such a setting, there is a query algorithm AE that with probability at least 0.99,
outputs a center set C such that Φ(C, X) ≤ (1 + ε) · ∆k (X). Moreover, the number of same-cluster
queries used by AE is O(k15 /ε8 ).
The previous theorems summarise the main results of this work which basically explores the
power of same-cluster queries in designing fast (1 + ε)-approximation algorithms for the k-means
problem. We will give the proofs of the above theorems in Sections 3, 4, and 5. There are some
other simple and useful contexts, where the SSAC framework gives extremely nice results. One
such context is the popular k-means++ seeding algorithm. This is an extremely simple sampling
based algorithm for the k-means problem that samples k centers in a sequence of k iterations. We
show that within the SSAC framework, a small modification of this sampling algorithm converts it
to one that gives constant factor approximation instead of O(log k)-approximation [AV07] that is
known. This is another witness to the power of same-cluster queries. We begin the technical part
of this work by discussing this result in Section 2. Some of the basic techniques involved in proving
our main results will be introduced while discussing this simpler context.
Other related work Clustering problems have been studied in different semi-supervised settings.
Basu et al. [BBM04] explored must-link and cannot-link constraints in their semi-supervised clustering formulation. In their framework, must-link and cannot-link constraints were provided explicitly as part of the input along with the cost of violating these constraints. They gave an active
learning formulation for clustering in which an oracle answers whether two query points belong to

the same cluster or not, and gave a clustering algorithm using these queries. However, they work
with a different objective function and there is no discussion on theoretical bounds on the number
of queries. In contrast, in our work we consider the k-means objective function and provide bounds
on approximation guarantee, required number of adaptive queries, and the running time. Balcan
and Blum [BB08] proposed an interactive framework for clustering with split/merge queries. Given
a clustering C = {C1 , . . .}, a user provides feedback by specifying that some cluster Cl should be
split, or clusters Ci and Cj should be merged. Awasthi et al. [ABV14] studied a local interactive
algorithm for clustering with split and merge feedbacks. Voevodski et al. [VBR+ 14] considered one
versus all queries where query answer for a point s ∈ X returns distances between s to all points in
X. For a k-median instance satisfying (c, ε)-approximation stability property [BBG09], the authors
found a clustering close to true clustering using only O(k) one versus all queries. Vikram and Dasgupta [VD16] designed an interactive bayesian hierarchical clustering algorithm. Given dataset X,
the algorithm starts with a candidate hierarchy T , and an initially empty set C of constraints. The
algorithm queries user with a subtree T |S of hierarchy T restricted to constant sized set S ⊂ X of
leaves. User either accepts T |S or provides a counterexample triplet ({a, b}, c) which the algorithm
adds to its set of constraints C, and updates T . They consider both random and adaptive ways to
select S to query T |S .
Our Techniques We now give a brief outline of the new ideas needed for our results. Many algorithms
for the k-means problem proceed by iteratively finding approximations to the optimal centers. One
such popular algorithm is the k-means++ seeding algorithm [AV07]. In this algorithm, one builds
a set of potential centers iteratively. We start with a set C initialized to the empty set. At each
step, we sample a point with probability proportional to the square of the distance from C, and
add it to C. Arthur and Vassilvitskii [AV07] showed that if we continue this process till |C| reaches
k, then the corresponding k-means solution has expected cost O(log k) times the optimal k-means
cost. Aggarwal et al. [ADK09] showed that if we continue this process till |C| reaches βk, for some
constant β > 1, then the corresponding k-means solution (where we actually open all the centers
in C) has cost which is within constant factor of the optimal k-means cost with high probability.
Ideally, one would like to stop when size of C reaches k and obtain a constant factor approximation
guarantee. We know from previous works [AV07, BR13, BJA16] that this is not possible in the
classical (unsupervised) setting. In this work, we show that one can get such a result in the SSAC
framework. A high-level way of analysing the k-means++ seeding algorithm is as follows. We first
observe that if we randomly sample a point from a cluster, then the expected cost of assigning all
points of this cluster to the sampled point is within a constant factor of the cost of assigning all
the points to the mean of this cluster. Therefore, it suffices to select a point chosen uniformly at
random from each of the clusters. Suppose the set C contains such samples for the first i clusters
(of an optimal solution). If the other clusters are far from these i clusters, then it is likely that
the next point added to C belongs to a new cluster (and perhaps is close to a uniform sample).
However to make this more probable, one needs to add several points to C. Further, the number
of samples that needs to be added to C starts getting worse as the value of i increases. Therefore,
the algorithm needs to build C till its size becomes O(k log k). In the SSAC framework, we can
tell if the next point added in C belongs to a new cluster or not. Therefore, we can always ensure
that |C| does not exceed k. To make this idea work, we need to extend the induction argument of
Arthur and Vassilvitskii [AV07] – details are given in Section 2.
We now explain the ideas for the PTAS for k-means. We consider the special case of k = 2.
Let X1 and X2 denote the optimal clusters with X1 being the larger cluster. Inaba et al. [IKI94]
showed that if we randomly sample about O(1/ε) points from a cluster, and let µ′ denote the mean
of this subset of sampled points, then the cost of assigning all points in the cluster to µ′ is within

(1 + ε) of the cost of assigning all these points to their actual mean (whp). Therefore, it is enough to
get uniform samples of size about O(1/ε) from each of the clusters. Jaiswal et al. [JKS14] had the
following approach for obtaining a (1 + ε)-approximation algorithm for k-means (with running time
being nd · f (k, ε), where f is an exponential function of k/ε) – suppose we sample about O(1/ε2 )
points from the input, call this sample S. It is likely to contain at least O(1/ε) from X1 , but we
do not know which points in S are from X1 . Jaiswal et al. addressed this problem by cycling over
all subsets of S. In the SSAC model, we can directly partition S into S ∩ X1 and S ∩ X2 using
|S| same-cluster queries. Having obtained such a sample S, we can get a close approximation to
the mean of X1 . So assume for sake of simplicity that we know µ1 , the mean of X1 . Now we are
faced with the problem of obtaining a uniform sample from X2 . The next idea of Jaiswal et al.
is to sample points with probability proportional to square of distance from µ1 . This is known as
D 2 -sampling. Suppose we again sample about O(1/ε2 ) such points, call this sample S ′ . Assuming
that the two clusters are far enough (otherwise the problem only gets easier), they show that S ′
will contain about O(1/ε2 ) points from X2 (with good probability). Again, in the SSAC model, we
can find this subset by |S ′ | queries – call this set S ′′ . However, the problem is that S ′′ may not
represent a uniform sample from X2 . For any point e ∈ X2 , let pe denote the conditional probability
of sampling e given that a point from X2 is sampled when sampled using D 2 -sampling. They showed
ε
, where m denotes the size of X2 . In order for the sampling lemma of Inaba et al.
pe is at least m
[IKI94] to work, we cannot work with approximately uniform sampling. The final trick of Jaiswal
et al. was to show that one can in fact get a uniform sample of size about O(ε|S ′′ |) = O(1/ε) from
S ′′ . The idea is as follows – for every element e ∈ S ′′ , we retain it with probability peεm (which is at
most 1), otherwise we remove it from S ′′ . It is not difficult to see that this gives a uniform sample
from X2 . The issue is that we do not know m. Jaiswal et al. again cycle over all subsets of S ′ –
we know that there is a (large enough) subset of S ′ which will behave like a uniform sample from
X2 . In the SSAC framework, we first identify the subset of S ′ which belongs to X2 , call this S ′′ (as
above). Now we prune some points from S ′′ such that the remaining points behave like a uniform
sample. This step is non-trivial because as indicated above, we do not know the value m. Instead,
2
ε
and m
for most of the points of X2 . Therefore, S ′′ is likely to
we first show that pe lies between m
εpe
contain such a nice point, call it v. Now, for every point e ∈ S ′′ , we retain it with probability 2p
v
(which we know is at most 1). This gives a uniform sample of sufficiently large size from X2 . For k
larger than 2, we generalize the above ideas using a non-trivial induction argument.

2

k-means++ within SSAC framework

The k-means++ seeding algorithm, also known as the D 2 -sampling algorithm, is a simple sampling
procedure that samples k centers in k iterations. The description of this algorithm is given below.
The algorithm picks the first center randomly from the set X of points and after having picked
the first (i − 1) centers denoted by Ci−1 , it picks a point x ∈ X to be the ith center with probability
proportional to minc∈Ci−1 ||x − c||2 . The running time of k-means++ seeding algorithm is clearly
O(nkd). Arthur and Vassilvitskii [AV07] showed that this simple sampling procedure gives an
O(log k) approximation in expectation for any dataset. Within the SSAC framework where the
algorithm is allowed to make same-cluster queries, we can make a tiny addition to the k-means++
seeding algorithm to obtain a query algorithm that gives constant factor approximation guarantee
and makes only O(k2 log k) same-cluster queries. The description of the query algorithm is given
in Table 1 (see right). In iteration i > 1, instead of simply accepting the sampled point x as the
ith center (as done in k-means++ seeding algorithm), the sampled point x is accepted only if it
belongs to a cluster other than those to which centers in Ci−1 belong (if this does not happen,

k-means++(X,k)
Query-k-means++(X, k)
- Randomly sample a point x ∈ X
- Randomly sample a point x ∈ X
- C ← {x}
- C ← {x}
- for i = 2 to k
- for i = 2 to k
- Sample x ∈ X using distribution D
- for j = 1 to ⌈log k⌉
defined as D(x) = Φ(C,{x})
- Sample x ∈ X using distribution D
Φ(C,X)
- C ← C ∪ {x}
defined as D(x) = Φ(C,{x})
Φ(C,X)
- return(C)
- if(NewCluster(C, x)){C ← C ∪ {x}; break}
- return(C)
NewCluster(C, x)
- If(∃c ∈ C s.t. SameCluster(c, x)) return(false)
- else return(true)
Table 1. k-means++ seeding algorithm (left) and its adaptation in the SSAC setting (right)

the sampling is repeated for at most ⌈log k⌉ times). Here is the main result that we show for the
query-k-means++ algorithm.
Theorem 6. Let X ⊆ Rd be any dataset containing n points and k > 1 be a positive integer. Let
C denote the output of the algorithm Query-k-means++(X, k). Then
E[Φ(C, X)] ≤ 24 · ∆k (X),
where ∆k (X) denotes the optimal cost for this k-means instance. Furthermore, the algorithm makes
O(k2 log k) same-cluster queries and the running time of the algorithm is O(nkd + k log k log n +
k2 log k).
The bound on the number of same-cluster queries is trivial from the algorithm description. For the
running time, it takes O(nd) time to update the distribution D which is updated k times. This
accounts for the O(nkd) term in the running time. Sampling an element from a distribution D
takes O(log n) time (if we maintain the cumulative distribution etc.) and at most O(k log k) points
are sampled. Moreover, determining whether a sampled point belongs to an uncovered cluster takes
O(k) time. So, the overall running time of the algorithm is O(nkd+k log k log n+k 2 log k). We prove
the approximation guarantee in the remaining discussion. We will use the following terminology. Let
the optimal k clusters for dataset X are given as X1 , ..., Xk . For any i, ∆i (X)
Pdenotes the optimal
cost of the i-means problem on dataset X. Given this, note that ∆k (X) = ki=1 ∆1 (Xi ). For any
non-empty center set C, we say that a point x is sampled from dataset X using D 2 -sampling w.r.t.
center set C if the sampling probability of x ∈ X is given by D(x) = Φ(C,{x})
Φ(C,X) .
The proof of Theorem 6 will mostly follow O(log k)-approximation guarantee proof of k-means++
seeding by Arthur and Vassilvitskii [AV07]. The next two lemmas from [AV07] are crucially used
in the proof of approximation guarantee.
Lemma 1. Let A be any optimal cluster and let c denote a point sampled uniformly at random
from A. Then E[Φ({c}, A)] ≤ 2 · ∆1 (A).
Lemma 2. Let C be any arbitrary set of centers and let A be any optimal cluster. Let c be a point
sampled with D 2 -sampling with respect to the center set C. Then E[Φ(C ∪{c}, A)|c ∈ A] ≤ 8·∆1 (A).
The first lemma says that a randomly sampled center from X provides a good approximation
(in expectation) to the cost of the cluster to which it belongs. The second lemma says that for any
center set C, given that a center c that is D 2 -sampled from X w.r.t. C belong to an optimal cluster
A, the conditional expectation of the cost of the cluster A with respect to center set C ∪ {c} is at

most 8 times the optimal cost of cluster A. Using the above two lemmas, let us try to qualitatively
see why the k-means++ seeding algorithm behave well. The first center belongs to some optimal
cluster A and from Lemma 1 we know that this center is good for this cluster. At the time the
ith center is D 2 -sampled, there may be some optimal clusters which are still costly with respect
to the center set Ci−1 . But then we can argue that it is likely that the ith sampled center c will
belong to one of these costly clusters, and conditioned on the center being from one such cluster
A, the cost of this cluster after adding c to the current center set is bounded using Lemma 2. The
formal proof of O(log k) approximation guarantee in [AV07] involves setting up a clever induction
argument. We give a similar induction based argument to prove Theorem 6. We prove the following
lemma (similar to Lemma 3.3 in [AV07]). We will need the following definitions: For any center set
C, an optimal cluster A is said to be “covered” if at least one point from A is in C, otherwise A is
said to be “uncovered”. Let T be a union of a subset of the optimal clusters, then we will use the
def. P
notation ΦOP T (T ) =
Xi ⊆T ∆1 (Xi ).

Lemma 3. Let C ⊆ X be any set of centers such that the number of uncovered clusters w.r.t. C
is u > 0. Let Xu denote the set of points of the uncovered clusters and Xc denote set of the points
of the covered clusters. Let us run t iterations of the outer for-loop in Query-k-means++ algorithm
such that t ≤ u ≤ k. Let C ′ denote the resulting set of centers after running t iterations of the outer
for-loop. Then the following holds:


u−t
t
′
· Φ(C, Xu ).
(1)
+
E[Φ(C , X)] ≤ (Φ(C, Xc ) + 8 · ΦOP T (Xu )) · 2 +
k
u

Proof. Let us begin by analysing what happens when starting with C, one iteration of the outer forloop in query-k-means++ is executed. The following two observations will be used in the induction
argument:
Φ(C,Xc )
c)
Observation 1: If Φ(C,X
Φ(C,X) ≥ 1/2, then we have Φ(C,Xc )+Φ(C,Xu ) ≥ 1/2 which implies that Φ(C, Xu ) ≤
Φ(C, Xc ), and also Φ(C, X) ≤ 2 · Φ(C, Xc ).
c)
Observation 2: If Φ(C,X
Φ(C,X) < 1/2, then the probability that no point will be added after one iteration

⌈log k⌉
log k
c)
= k1 .
is given by Φ(C,X
< 12
Φ(C,X)

We will now proceed by induction. We show that if the statement holds for (t − 1, u) and
(t − 1, u − 1), then the statement holds for (t, u). In the basis step, we will show that the statement
holds for t = 0 and u > 0 and u = t = 1.
Basis step: Let us first prove the simple case of t = 0 and u > 0. In this case, C ′ = C. So, we
have E[Φ(C ′ , X)] = Φ(C, X) which is at most the RHS of (1). Consider the case when u = t = 1.
This means that there is one uncovered cluster and one iteration of the outer for-loop is executed.
If a center from the uncovered cluster is added, then E[Φ(C ′ , X)] ≤ Φ(C, Xc ) + 8 · ΦOP T (Xu )
and if no center is picked, then Φ(C ′ , X) = Φ(C, X). The probability of adding a center from the
log k

c)
. So, we get E[Φ(C ′ , X)] ≤ p · (Φ(C, Xc ) + 8 ·
uncovered cluster is given by p = 1 − Φ(C,X
Φ(C,X)
ΦOP T (Xu )) + (1 − p) · Φ(C, X). Note that this is upper bounded by the RHS of (1) by observing
c)
that 1 − p ≤ Φ(C,X
Φ(C,X) .
Inductive step: As stated earlier, we will assume that the statement holds for (t − 1, u) and
def.

c)
1
(t − 1, u − 1) and we will show that the statement holds for (t, u). Suppose p = Φ(C,X
Φ(C,X) ≥ 2 , then
Φ(C, X) ≤ 2 · Φ(C, Xc ) and so Φ(C ′ , X) ≤ Φ(C, X) ≤ 2 · Φ(C, Xc ) which is upper bounded by the
RHS of (1). So, the statement holds for (t, u) (without even using the induction assumption). So,
for the rest of the discussion, we will assume that p < 1/2. Let us break the remaining analysis

into two cases – (i) no center is added in the next iteration of the outer for-loop, and (ii) a center
is added. In case (i), u does not change, t decreases by 1, and the covered and uncovered clusters
remain the same after the iteration. So the contribution of this case to E[Φ(C ′ , X)] is at most




t−1
u−t+1
⌈log k⌉
p
· (Φ(C, Xc ) + 8 · ΦOP T (Xu )) · 2 +
· Φ(C, Xu )
(2)
+
k
u
Now, consider case (ii). Let A be any uncovered cluster w.r.t. center set C. For any point a ∈ A,
let pa denote the conditional probability of sampling a conditioned on sampling a point from A.
Also, let φa denote the cost of A given a is added as a center. That is, φa = Φ(C ∪ {a}, A). The
contribution of A to the expectation E[Φ(C ′ , X)] using the induction hypothesis is:
(1 − p⌈log k⌉ ) ·

Φ(C, A) X
pa
Φ(C, Xu )
a ∈A





t−1
u−t
· (Φ(C, Xc ) + φa + 8 · ΦOP T (Xu ) − 8 · ∆1 (A)) · 2 +
· (Φ(C, Xu ) − Φ(C, A))
+
k
u−1
This is at most


t−1
u−t
· (Φ(C, Xu ) − Φ(C, A))
(1 − p
(Φ(C, Xc ) + 8 · ΦOP T (Xu )) · 2 +
+
k
u−1
P
The previous inequality follows from the fact that a∈A pa φa ≤ 8 · ∆1 (A) from Lemma 2. Summing
over all uncovered clusters, the overall contribution in case (ii) is at most:





Φ(C, Xu )
t−1
u−t
· Φ(C, Xu ) −
(1 − p⌈log k⌉ ) · (Φ(C, Xc ) + 8 · ΦOP T (Xu )) · 2 +
+
k
u−1
u
⌈log k⌉

Φ(C, A)
)·
Φ(C, Xu )





P
The above bound is obtained using the fact that A is uncovered Φ(C, A)2 ≥ u1 Φ(C, Xu )2 . So the
contribution is at most




t−1
u−t
⌈log k⌉
(1 − p
) · (Φ(C, Xc ) + 8 · ΦOP T (Xu )) · 2 +
· Φ(C, Xu )
(3)
+
k
u
Combining inequalities (2) and (3), we get the following:




t−1
Φ(C, Xu )
u−t
′
E[Φ(C , X)] ≤ (Φ(C, Xc ) + 8 · ΦOP T (Xu )) · 2 +
· Φ(C, Xu ) + p⌈log k⌉ ·
+
k
u
u




t−1
u−t
= (Φ(C, Xc ) + 8 · ΦOP T (Xu )) · 2 +
· Φ(C, Xu ) +
+
k
u


Φ(C, Xc ) ⌈log k⌉ Φ(C, Xu )
·
Φ(C, X)
u




Φ(C, Xc )
u−t
t−1
· Φ(C, Xu ) +
+
≤ (Φ(C, Xc ) + 8 · ΦOP T (Xu )) · 2 +
k
u
ku
(using the Observation 2, that is p⌈log k⌉ ≤ 1/k)


u−t
t
· Φ(C, Xu )
+
≤ (Φ(C, Xc ) + 8 · ΦOP T (Xu )) · 2 +
k
u
This completes the inductive argument and the proof.

⊔
⊓

Let us now conclude the proof of Theorem 6 using the above lemma. Consider the center set C
before entering the outer for-loop. This contains a single center c chosen randomly from the dataset
X. Let c belong to some optimal cluster A. Let C ′ denote the center set after the execution of the
outer for-loop completes. Applying the above lemma with u = t = k − 1, we get:


k−1
′
E[Φ(C , X)] ≤ (Φ(C, A) + 8 · ∆k (X) − 8 · ∆1 (A)) · 2 +
k
≤ 3 · (2 · ∆1 (A) + 8 · ∆k (X) − 8 · ∆1 (A)) (using Lemma 1)
≤ 24 · ∆k (X)

3

Query Approximation Algorithm (proof of Theorem 3)

As mentioned in the introduction, our query algorithm is based on the D 2 -sampling based algorithm
of Jaiswal et al. [JKS14, JKY15]. The algorithm in these works give a (1 + ε)-factor approximation
for arbitrary small ε > 0. The running time of these algorithms are of the form nd · f (k, ε), where
f is an exponential function of k/ε. We now show that it is possible to get a running time which
is polynomial in n, k, d, 1/ε in the SSAC model. The main ingredient in the design and analysis of
the sampling algorithm is the following lemma by Inaba et al. [IKI94].
Lemma 4 ([IKI94]). Let S be a set of points obtained by independently sampling M points uniformly at random with replacement from a point set X ⊂ Rd . Then for any δ > 0,




1
Pr Φ({µ(S)}, X) ≤ 1 +
· ∆1 (X) ≥ (1 − δ).
δM
Here µ(S) denotes the geometric centroid of the set S. That is µ(S) =

P

s∈S

s

|S|

Our algorithm Query-k-means is described in Table 2. It maintains a set C of potential centers of
the clusters. In each iteration of step (3), it adds one more candidate center to the set C (whp), and
so, the algorithm stops when |C| reaches k. For sake of explanation, assume that optimal clusters
are X1 , X2 , . . . , Xk with means µ1 , . . . , µk respectively. Consider the ith iteration of step (3). At this
time |C|= i − 1, and it has good approximations to means of i − 1 clusters among X1 , . . . .Xk . Let us
call these clusters covered. In Step (3.1), it samples N points, each with probability proportional to
square of distance from C (D 2 -sampling). Now, it partitions this set, S, into S ∩ X1 , . . . , S ∩ Xk in
the procedure UncoveredClusters, and then picks the partition with the largest size such that the
corresponding optimal cluster Xj is not one of the (i − 1) covered clusters. Now, we would like to
get a uniform sample from Xj – recall that S ∩Xj does not represent a uniform sample. However, as
mentioned in the introduction, we need to find an element s of Xj for which the probability of being
in sampled is small enough. Therefore, we pick the element in S ∩ Xj for which this probability is
smallest (and we will show that it has the desired properties). The procedure UncoveredCluster
returns this element s. Finally, we choose a subset T of S ∩ Xj in the procedure UniformSample.
This procedure is designed such that each element of Xj has the same probability of being in T .
In step (3.4), we check whether the multi-set T is of a desired minimum size. We will argue that
the probability of T not containing sufficient number of points is very small. If we have T of the
desired size, we take its mean and add it to C in Step (3.6).
We now formally prove the approximation guarantee of the Query-k-means algorithm.
Theorem 7. Let 0 < ε ≤ 1/2, k be any positive integer, and X ⊆ Rd . There exists an algorithm
that runs in time O(ndk9 /ε4 ) and with probability at least 14 outputs a center set C such that
Φ(C, X) ≤ (1 + ε) · ∆k (X). Moreover, the number of same-cluster queries used by the algorithm is
O(k9 /ε4 ).

12

3

23

2

Constants: N = (2 ε2)k , M = 64k
, L = (2 ε4)k
ε
Query-k-means(X, k, ε)
UncoveredCluster(C, S, R)
(1) R ← ∅
- For all i ∈ {1, ..., k}: Si ← ∅
(2) C ← ∅
-i←1
(3) for i = 1 to k
- For all y ∈ R: {Si ← y; i++}
(3.1) D2 -sample a multi-set S of N points
- For all s ∈ S:
from X with respect to center set C
- If (∃j, y s.t. y ∈ Sj & SameCluster(s, y))
(3.2) s ← UncoveredCluster(C, S, R)
- Sj ← Sj ∪ {s}
(3.3) T ← UniformSample(X, C, s)
- else
(3.4) If (|T |< M ) continue
- Let i be any index s.t. Si is empty
(3.5) R ← R ∪ {s}
- Si ← {s}
(3.6) C ← C ∪ µ(T )
- Let Si be the largest set such that i > |R|
(4) return(C)
- Let s ∈ Si be the element with smallest
UniformSample(X, C, s)
value of Φ(C, {s}) in Si
-T ←∅
- return(s)
- For i = 1 to L:
- D2 -sample a point x from X with respect to center set C
- If (SameCluster(s, x))


- With probability

ε
128

·

Φ(C,{s})
Φ(C,{x})

add x in multi-set T

- return(T )
Table 2. Approximation algorithm for k-means(top-left frame). Note that µ(T ) denotes the centroid of T and D2 sampling w.r.t. empty center set C means just uniform sampling. The algorithm UniformSample(X, C, s) (bottom-left)
returns a uniform sample of size Ω(1/ε) (w.h.p.) from the optimal cluster to which point s belongs.

Note that the success probability of the algorithm may be boosted by repeating it a constant
number of times. This will also prove our main theorem (that is, Theorem 3). We will assume that
the dataset X satisfies (k, ε)-irreducibility property defined next. We will later drop this assumption
using a simple argument and show that the result holds for all datasets. This property was also
used in some earlier works [KSS10, JKS14].
Definition 3 (Irreducibility). Let k be a positive integer and 0 < ε ≤ 1. A given dataset X ⊆ Rd
is said to be (k, ε)-irreducible iff
∆k−1 (X) ≥ (1 + ε) · ∆k (X).
Qualitatively, what the irreducibility assumption implies is that the optimal solution for the
(k − 1)-means problem does not give a (1+ ε)-approximation to the k-means problem. The following
useful lemmas are well known facts.
Lemma 5. For any dataset X ⊆ Rd and a point c ∈ Rd , we have:
Φ({c}, X) = Φ(µ(X), X) + |X|·||c − µ(X)||2 .
Lemma 6 (Approximate Triangle Inequality). For any three points p, q, r ∈ Rd , we have
||p − q||2 ≤ 2(||p − r||2 +||r − q||2 )
Let X1 , ..., Xk be optimal clusters of the dataset X for the k-means objective. Let µ1 , ..., µk
denote the corresponding
optimal k centers. That is, ∀i, µi = µ(Xi ). For all i, let mi = |Xi |. Also,
P
for all i, let ri =
5

x∈Xi ||x−µi ||

mi

2

. The following useful lemma holds due to irreducibility.5

This is Lemma 4 from [JKS14]. We give the proof here for self-containment.

Lemma 7. For all 1 ≤ i < j ≤ k, ||µi − µj ||2 ≥ ε · (ri + rj ).
Proof. For the sake of contradiction, assume that ||µi − µj ||2 < ε · (ri + rj ). WLOG assume that
mi > mj . We have:
Φ({µi }, Xi ∪ Xj ) = mi ri + mj rj + mj ||µi − µj ||2

(using Lemma 5)

≤ (1 + ε) · mi ri + (1 + ε) · mj rj

(since mi > mj )

≤ mi ri + mj rj + mj · ε · (ri + rj )

≤ (1 + ε) · Φ({µi , µj }, Xi ∪ Xj )

This implies that the center set {µ1 , ..., µk } \ {µj } gives a (1 + ε)-approximation to the k-means
objective which contradicts with the (k, ε)-irreducibility assumption on the data.
⊔
⊓
Consider the algorithm Query-k-means in Figure 2. Let Ci = {c1 , ..., ci } denote the set of centers
at the end of the ith iteration of the for loop. That is, Ci is the same as variable C at the end of
iteration i. We will prove Theorem 7 by inductively arguing that for every i, there are i distinct
clusters for which centers in Ci are good in some sense. Consider the following invariant:
P(i): There exists a set of i distinct clusters Xj1 , Xj2 , ..., Xji such that

ε
· ∆1 (Xjr ).
∀r ∈ {1, ..., i}, Φ({cr }, Xjr ) ≤ 1 +
16
P
ε
Note that a trivial consequence of P (i) is Φ(Ci , Xj1 ∪ ... ∪ Xji ) ≤ (1 + 16
) · ir=1 ∆1 (Xjr ). We
will show that for all i, P (i) holds with probability at least (1 − 1/k)i . Note that the theorem
follows if P (k) holds with probability at least (1 − 1/k)k . We will proceed using induction. The
base case P (0) holds since C0 is the empty set. For the inductive step, assuming that P (i) holds
with probability at least (1 − 1/k)i for some arbitrary i ≥ 0, we will show that P (i + 1) holds with
probability at least (1 − 1/k)i+1 . We condition on the event P (i) (that is true with probability
at least (1 − 1/k)i ). Let Ci and Xj1 , ..., Xji be as guaranteed by the invariant P (i). For ease of
notation and without loss of generality, let us assume that the index jr is r. So, Ci gives a good
approximation w.r.t. points in the set X1 ∪ X2 ∪ .... ∪ Xi and these clusters may be thought of as
“covered” clusters (in the approximation sense). Suppose we D 2 -sample a point p w.r.t. center set
Ci . The probability that p belongs to some “uncovered cluster” Xr where r ∈ [i + 1, k] is given
i ,Xr )
2
as Φ(C
Φ(Ci ,X) . If this quantity is small, then the points sampled using D sampling in subsequent
iterations may not be good representatives for the uncovered clusters. This may cause the analysis
to break down. However, we argue that since our data is (k, ε)-irreducible, this does not occur. 6
Lemma 8.

Φ(Ci ,Xi+1 ∪...∪Xk )
Φ(Ci ,X)

≥ 4ε .

Proof. For the sake of contradiction, assume that the above statement does not hold. Then we
have:
Φ(Ci , X) = Φ(Ci , X1 ∪ ... ∪ Xi ) + Φ(Ci , Xi+1 ∪ ... ∪ Xk )
(ε/4)
≤ Φ(Ci , X1 ∪ ... ∪ Xi ) +
· Φ(Ci , X1 ∪ ... ∪ Xi ) (using our assumption)
1 − (ε/4)
1
· Φ(Ci , X1 ∪ ... ∪ Xi )
=
1 − ε/4
6

This is Lemma 5 in [JKS14]. We give the proof for self-containment.

≤

i
1 + ε/16 X
∆1 (Xj ) (using invariant)
·
1 − ε/4
j=1

≤ (1 + ε) ·

k
X

∆1 (Xj )

j=1

⊔
⊓

This contradicts with the (k, ε)-irreducibility of X.
The following simple corollary of the above lemma will be used in the analysis later.
Corollary 1. There exists an index j ∈ {i + 1, ..., k} such that

Φ(Ci ,Xj )
Φ(Ci ,X)

≥

ε
4k .

The above corollary says that there is an uncovered cluster which will have a non-negligible
representation in the set S that is sampled in iteration (i + 1) of the algorithm Query-k-means.
The next lemma shows that conditioned on sampling from an uncovered cluster l ∈ {i + 1, ..., k},
ε
times its sampling probability if it were
the probability of sampling a point x from Xl is at least 64
ε
· m1l ). 7
sampled uniformly from Xl (i.e., with probability at least 64
Lemma 9. For any l ∈ {i + 1, ..., k} and x ∈ Xl ,

Φ(Ci ,{x})
Φ(Ci ,Xl )

≥

ε
64

·

1
ml .

Proof. Let t ∈ {1, ..., i} be the index such that x is closest to ct among all centers in Ci . We have:
Φ(Ci , Xl ) = ml · rl + ml · ||µl − ct ||2

(using Lemma 5)
2

≤ ml · rl + 2ml · (||µl − µt || +||µt − ct ||2 ) (using Lemma 6)
ε
≤ ml · rl + 2ml · (||µl − µt ||2 + · rt ) (using invariant and Lemma 5)
16

Also, we have:
||x − µt ||2
− ||µt − ct ||2 (using Lemma 6)
2
||µl − µt ||2
≥
− ||µt − ct ||2 (since ||x − µt ||≥ ||µl − µt ||/2)
8
ε
||µl − µt ||2
−
· rt (using invariant and Lemma 5)
≥
8
16
||µl − µt ||2
≥
(using Lemma 7)
16

Φ(Ci , {x}) = ||x − ct ||2 ≥

Combining the inequalities obtained above, we get the following:
||µl − µt ||2
Φ(Ci , {x})

≥
Φ(Ci , Xl )
16 · ml · rl + 2||µl − µt ||2 + 8ε · rt
1
1
ε
1
≥
·
≥
·
16 · ml (1/ε) + 2 + (1/8)
64 ml
This completes the proof of the lemma.

⊔
⊓

With the above lemmas in place, let us now get back to the inductive step of the proof. Let
J ⊆ {i + 1, ..., k} denote the subset of indices (from the uncovered cluster indices) such that
7

This is Lemma 6 from [JKS14]. We give the proof for self-containment.

Φ(Ci ,Xj )
ε
Φ(Ci ,X) ≥ 8k . For any
2
i ,{y})
Yj , Φ(C
Φ(Ci ,Xj ) ≤ mj . That

∀j ∈ J,

index j ∈ J, let Yj ⊆ Xj denote the subset of points in Xj such that

is, Yj consists of all the points such that the conditional probability
∀y ∈
of sampling any point y in Yj , given that a point is sampled from Xj , is upper bounded by 2/mj .
Note that from Lemma 9, the conditional probability of sampling a point x from Xj , given that a
ε
· m1j . This gives the following simple and useful
point is sampled from Xj , is lower bounded by 64
lemma.
Lemma 10. For all j ∈ {i + 1, ..., k} the following two inequalities hold:
Φ(C ,Y )

Φ(C ,X )

j
j
ε
1. Φ(Cii ,X)
· Φ(Cii ,X)
≥ 128
, and
2. For any y ∈ Yj and any x ∈ Xj ,

ε
128

· Φ(Ci , {y}) ≤ Φ(Ci , {x}).
Φ(Ci ,{y})
ε
Φ(Ci ,Xj ) ≥ 64
1
ε
i ,{x})
Xj , Φ(C
Φ(Ci ,Xj ) ≥ 64 · mj

Proof. Inequality (1) follows from the fact that |Yj |≥ mj /2, and
Xj . Inequality (2) follows from the fact that for all x ∈

i ,{y})
Yj , Φ(C
Φ(Ci ,Xj ) ≤

2
mj .

·

1
mj

for all y ∈

and for all y ∈
⊔
⊓

Let us see the outline of our plan before continuing with our formal analysis. What we hope to
get in line (3.2) of the algorithm is a point s that belongs to one of the uncovered clusters with index
in the set J. That is, s belongs to an uncovered cluster that is likely to have a good representation
in the D 2 -sampled set S obtained in line (3.1). In addition to s belonging to Xj for some j ∈ J, we
would like s to belong to Yj . This is crucial for the uniform sampling in line (3.3) to succeed. We
will now show that the probability of s returned in line (3.2) satisfies the above conditions is large.
Lemma 11. Let S denote the D 2 -sample obtained w.r.t. center set Ci in line (3.1) of the algorithm.
Pr[∃j ∈ J such that S does not contain any point from Yj ] ≤

1
.
4k

Proof. We will first get bound on the probability for a fixed j ∈ J and then use the union bound.
Φ(C ,Yj )
ε
ε2
ε
From property (1) of Lemma 10, we have that for any j ∈ J, Φ(Cii ,X)
· 8k
= (210
≥ 128
. Since the
)k
12

3

number of sampled points is N = (2 ε2)k , we get that the probability that S has no points from Yj
is at most 4k12 . Finally, using the union bound, we get the statement of the lemma.
⊔
⊓

Lemma 12. Let S denote the D 2 -sample obtained w.r.t. center set Ci in line (3.1) of the algorithm
and let Sj denote the representatives of Xj in S. Let max = arg maxj∈{i+1,...,k}|Sj |. Then Pr[max ∈
/
1
J] ≤ 4k .
Φ(C ,X )

j
ε
Proof. From Corollary 1, we know that there is an index j ∈ {i + 1, ..., k} such that Φ(Cii ,X)
.
≥ 4k
ε
Let α = N · 4k . The expected number of representatives from Xj in S is at least α. So, from
Chernoff bounds, we have:
Pr[|Sj |≤ 3α/4] ≤ e−α/32

On the other hand, for any r ∈ {i + 1, ..., k} \ J, the expected number of points in S from Xr is at
ε
· N = α/2. So, from Chernoff bounds, we have:
most 8k
Pr[|Sr |> 3α/4] ≤ e−α/24
So, the probability that there exists such an r is at most k · e−α/24 by union bound. Finally, the
probability that max ∈
/ J is at most Pr[|Sj |≤ 3α/4] + Pr[∃r ∈ {i + 1, ..., k} \ J||Sr |> 3α/4] which
12 3
1
⊔
⊓
is at most 4k due to our choice of N = (2 ε2)k .

1
From the previous two lemmas, we get that with probability at least (1 − 2k
), the s returned
in line (3.2) belongs to Yj for some j ∈ J. Finally, we will need the following claim to argue that
the set T returned in line (3.3) is a uniform sample from one of the sets Xj for j ∈ {i + 1, ..., k}.

Lemma 13. Let S denote the D 2 -sample obtained w.r.t. center set Ci in line (3.1) and s be the
point returned in line (3.2) of the algorithm. Let j denote the index of the cluster to which s belongs.
1
), T returned in line (3.3) is a uniform
If j ∈ J and s ∈ Yj , then with probability at least (1 − 4k
64k
sample from Xj with size at least ε .
Proof. Consider the call to sub-routine UniformSample(X, Ci, s) with s as given in the statement
of the lemma. If j is the index of the cluster to which s belongs, then j ∈ J and s ∈ Yj . Let us define
L random variables Z1 , ..., ZL one for every iteration of the sub-routine. These random variables
are defined as follows: for any r ∈ [1, L], if the sampled point x belongs to the same cluster as s
and it is picked to be included in multi-set S, then Zr = x, otherwise Zr = ⊥. We first note that
for any r and any x, y ∈ Xj , Pr[Zr = x] = Pr[Zr = y]. This is because for any x ∈ Xj , we have
ε

·Φ(C ,{s})

ε

·Φ(C ,{s})

i
i
ε
i ,{s})
i ,{x})
128
128
· Φ(C
Pr[Zr = x] = Φ(C
= 128
≤1
Φ(Ci ,X) · Φ(Ci ,{x})
Φ(Ci ,X) . It is important to note that
Φ(Ci ,{x})
from property (2) of Lemma 10 and hence valid in the probability calculations above.
Let us now obtain a bound on the size of T . Let Tr = I(Zr ) be the indicator variable that is 1
if Zr 6= ⊥ and 0 otherwise. Using the fact that j ∈ J, we get that for any r:
P
ε
ε
ε
ε
ε3
x∈Xj Φ(Ci , {s})
E[Tr ] = Pr[Tr = 1] =
·
≥
·
·
= 16 .
128
Φ(Ci , X)
128 8k 64
(2 )k

Given that L =

223 k 2
,
ε4

applying Chernoff bounds, we get the following:


 

64k
1
64k
= 1 − Pr |T |≤
≥ 1−
Pr |T |≥
ε
ε
4k


This completes the proof of the lemma.

⊔
⊓

Since a suitable s (as required by the above lemma) is obtained in line (3.2) with probability at
1
least (1− 2k
), the probability that T obtained in line (3.3) is a uniform sample from some uncovered
1
1
)·(1− 4k
). Finally, the probability that the centroid µ(T ) of the multi-set
cluster Xj is at least (1− 2k
1
) using Inaba’s lemma. Combining
T that is obtained is a good center for Xj is at least (1 − 4k
1
everything, we get that with probability at least (1 − k ) an uncovered cluster will be covered in the
ith iteration. This completes the inductive step and hence the approximation guarantee of (1 + ε)
holds for any dataset that satisfies the (k, ε)-irreducibility assumption. For the number of queries
and running time, note that every time sub-routine UncoveredCluster is called, it uses at most
kN same cluster queries. For the subroutine UniformSample, the number of same-cluster queries
made is L. So, the total number of queries is O(k(kN + L)) = O(k5 /ε4 ). More specifically, we have
proved the following theorem.
Theorem 8. Let 0 < ε ≤ 1/2, k be any positive integer, and X ⊆ Rd such that X is (k, ε)irrducible. Then Query-k-means(X, k, ε) runs in time O(ndk5 /ε4 ) and with probability at least
(1/4) outputs a center set C such that Φ(C, X) ≤ (1 + ε) · ∆k (X). Moreover, the number of samecluster queries used by Query-k-means(X, k, ε) is O(k5 /ε4 ).
To complete the proof of Theorem 7, we must remove the irreducibility assumption in the above
theorem. We do this by considering the following two cases:

ε
1. Dataset X is (k, (4+ε/2)k
)-irreducible.
ε
2. Dataset X is not (k, (4+ε/2)k )-irreducible.

In the former case, we can apply Theorem 8 to obtain Theorem 7. Now, consider the latter
ε
case. Let 1 < i ≤ k denote the largest index such that X is (i, (1+ε/2)k
)-irreducible, otherwise i = 1.
Then we have:
k−i


ε
ε
· ∆k (X).
· ∆k (X) ≤ 1 +
∆i (X) ≤ 1 +
(4 + ε/2)k
4
This means that a (1 + ε/4)-approximation for the i-means problem on the dataset X gives the
desired approximation for the k-means problem. Note that our approximation analysis works for the
i-means problem with respect to the algorithm being run only for i steps in line (3) (instead of k).
That is, the centers sampled in the first i iterations of the algorithm give a (1+ε/16)-approximation
for the i-means problem for any fixed i. This simple observation is sufficient for Theorem 7. Note
since Theorem 8 is used with value of the error parameter as O(ε/k), the bounds on the query and
running time get multiplied by a factor of k4 .

4

Query Lower Bound (proof of Theorem 4)

In this section, we will obtain a conditional lower bound on the number of same-cluster queries
assuming the Exponential Time Hypothesis (ETH). This hypothesis has been used to obtain lower
bounds in various different contexts (see [Man16] for reference). We start by stating the Exponential
Time Hypothesis (ETH).
Hypothesis 1 (Exponential Time Hypothesis (ETH)[IP01, IPZ01]): There does not exist
an algorithm that can decide whether any 3-SAT formula with m clauses is satisfiable with
running time 2o(m) .
Since we would like to obtain lower bounds in the approximation domain, we will need a gap
version of the above ETH hypothesis. The following version of the PCP theorem will be very useful
in obtaining a gap version of ETH.
Theorem 9 (Dinur’s PCP Theorem [Din07]). For some constants ε, d > 0, there exists a
polynomial time reduction that takes a 3-SAT formula ψ with m clauses and produces another
3-SAT formula φ with m′ = O(m polylog m) clauses such that:
– If ψ is satisfiable, then φ is satisfiable,
– if ψ is unsatisfiable, then val(φ) ≤ 1 − ε, and
– each variable of φ appears in at most d clauses.
Here val(φ) denotes the maximum fraction of clauses of φ that are satisfiable by any assignment.
The following new hypothesis follows from ETH and will be useful in our analysis.
Hypothesis 2: There exists constants ε, d > 0 such that the following holds: There does
not exist an algorithm that, given a 3-SAT formula ψ with m clauses with each variable
appearing in atmost d clauses, distinguishes whether ψ is satisfiable or val(ψ) ≤ (1 − ε),
Ω

runs in time 2

m
poly log m

.

The following simple lemma follows from Dinur’s PCP theorem given above.

Lemma 14. If Hypothesis 1 holds, then so does Hypothesis 2.
We now see a reduction from the gap version of 3-SAT to the gap version of the Vertex Cover
problem that will be used to argue the hardness of the k-means problem. The next result is a
standard reduction and can be found in a survey by Luca Trevisan [Tre04].
Lemma 15. Let ε, d > 0 be some constants. There is a polynomial time computable function
mapping 3-SAT instances ψ with m variables and where each variable appears in at most d clauses,
into graphs Gψ with 3m vertices and maximum degree O(d) such that if ψ is satisfiable, then Gψ
has a vertex cover of size at most 2m and if val(ψ) ≤ (1 − ε), then every vertex cover of Gψ has
size at least 2m(1 + ε/2).
We formulate the following new hypothesis that holds given that hypothesis 2 holds. Eventually,
we will chain all these hypothesis together.
Hypothesis 3: There exists constants ε, d > 0 such that the following holds: There does not
exist an algorithm that, given a graph G with n vertices and maximum degree d, distinguishes
between the case when G has a vertex cover of size at most
2n/3 and the case when G has

a vertex cover of size at least

2n
3

Ω

· (1 + ε), runs in time 2

n
poly log n

.

The following lemma is a simple implication of Lemma 15
Lemma 16. If Hypothesis 2 holds, then so does Hypothesis 3.
We are getting closer to the k-means problem that has a reduction from the vertex cover problem
on triangle-free graphs [ACKS15]. So, we will need reductions from vertex cover problem to vertex
cover problem on triangle-free graphs and then to the k-means problem. These two reductions are
given by Awasthi et al. [ACKS15].
Lemma 17 (Follows from Theorem 21 [ACKS15]). Let ε, d > 0 be some constants. There is
a polynomial-time computable function mapping any graph G = (V, E) with maximum degree d to
a triangle-free graph Ĝ = (V̂ , Ê) such that the following holds:
3 2
– 
|V̂ |= poly(d,1/ε)· |V | and maximum
degree

 of verticesin Ĝ is O(d /ε ), and
Ĝ)|
≤ 1 − |V C(
.
– 1 − |V C(G)|
≤ (1 + ε) · 1 − |V C(G)|
|V |
|V |
|V̂ |

Here V C(G) denote the size of the minimum vertex cover of G.
We can formulate the following hypothesis that will follow from Hypothesis 3 using the above
lemma.
Hypothesis 4: There exists constants ε, d > 0 such that the following holds: There does
not exist an algorithm that, given a triangle-free graph G with n vertices and maximum
2n
degree d, distinguishes between the case when G has a vertex cover of size at most
3 and

the case when G has a vertex cover of size at least

2n
3

Ω

· (1 + ε), runs in time 2

The next claim is a simple application of Lemma 17.
Lemma 18. If Hypothesis 3 holds, then so does Hypothesis 4.

n
poly log n

.

Finally, we use the reduction from the vertex cover problem in triangle-free graphs to the kmeans problem to obtain the hardness result for the k-means problem. We will use the following
reduction from Awasthi et al. [ACKS15].
Lemma 19 (Theorem 3 [ACKS15]). There is an efficient reduction from instances of Vertex
Cover (in triangle free graphs) to those of k-means that satisfies the following properties:
– if the Vertex Cover instance has value k, then the k-means instance has cost at most (m − k)
– if the Vertex Cover instance has value at least k(1 + ε), then the optimal k-means cost is at least
m − (1 − Ω(ε))k. Here ε is some fixed constant > 0.
Here m denotes the number of edges in the vertex cover instance.
The next hypothesis follows from Hypothesis 4 due to the above lemma.
Hypothesis 5: There exists constant c > 1 such that the following holds: There does not
exist an algorithm that gives
guarantee of c for the k-means problem that
 an approximation

Ω

runs in time poly(n, d) · 2

k
poly log k

.

Claim. If Hypothesis 4 holds, then so does Hypothesis 5.
Now using Lemmas 14, 16, 18, and 4, get the following result.
Lemma 20. If the Exponential Time Hypothesis (ETH) holds then there exists a constant c > 1
such that any c-approximation
algorithm for the k-means problem cannot have running time better


Ω

than poly(n, d) · 2

k
poly log k

.

This proves Theorem 4 since if there is a query algorithm that runs in time poly(n, d, k) and
makes polyklog k same-cluster queries, then we can convert it to a non-query algorithm that runs in
k

time poly(n, d) · 2 poly log k in a brute-force manner by trying out all possible answers for the queries
and then picking the best k-means solution.

5

Query Approximation Algorithm with Faulty Oracle

In this section, we describe how to extend our approximation algorithm for k-means clustering
in the SSAC framework when the oracle is faulty. That is, the answer to the same-cluster query
may be incorrect. Let us denote the faulty same-cluster oracle as OE . We consider the following
error model: for a query with points u and v, the query answer OE (u, v) is wrong independently
with probability at most q that is strictly less than 1/2. More specifically, if u and v belong to the
same optimal cluster, then OE (u, v) = 1 with probability at least (1 − q) and OE (u, v) = 0 with
probability at most q. Similarly, if u and v belong to different optimal clusters, then OE (u, v) = 1
with probability at most q and OE (u, v) = 0 with probability at least (1 − q).
The modified algorithm giving (1 + ε)-approximation for k-means with faulty oracle OE is given
in Figure 3. Let X1 , . . . , Xk denote the k optimal clusters for the dataset X. Let C = {c1 , . . . , ci }
denote the set of i centers chosen by the algorithm at the end of iteration i. Let S denote the
sample obtained using D 2 -sampling in the (i + 1)st iteration. The key idea for an efficient (1 + ε)approximation algorithm for k-means in the SSAC framework with a perfect oracle was the following.
Given a sample S, we could compute using at most k|S| same-cluster queries the partition S1 , . . . , Sk
of S among the k optimal clusters such that Sj = S ∩ Xj for all j. In the following, we discuss how
we achieve this partitioning of S among k optimal clusters when the oracle OE is faulty.

We reduce the problem of finding the partitions of S among the optimal clusters to the problem
of recovering dense (graph) clusters in a stochastic block model (SBM). An instance of an SBM is
created as follows. Given any arbitrary partition V1 , . . . , Vk of a set V of vertices, an edge is added
between two vertices belonging to the same partition with probability at least (1 − q) and between
two vertices in different partitions with probability at most q. We first construct an instance I
of an SBM using the sample S. By querying the oracle OE with all pairs of points u, v in S, we
obtain a graph I on |S| vertices, where vertices in I correspond to the points in S, and an edge
exists in I between vertices u and v if OE (u, v) = 1. Since oracle OE errs with probability at most
q, for any u, v ∈ Sj for some j ∈ [k], there is an edge between u and v with probability at least
(1 − q). Similarly, there is an edge (u, v) ∈ I for any two points u ∈ Sy and v ∈ Sz , y 6= z belonging
to different optimal clusters with probability at most q. Note that the instance I created in this
manner would be an instance of an SBM. Since q < 1/2, this procedure, with high probability,
creates more edges between vertices belonging to the same partition than the number of edges
between vertices in different partitions. Intuitively, the partitions of S would correspond to the
dense (graph) clusters in SBM instance I, and if there were no errors, then each partition would
correspond to a clique in I. One way to figure out the partitions S1 , . . . , Sk would be to retrieve the
dense (graph) clusters from the instance I. Ailon et al. [ACX15] gave a randomized algorithm to
retrieve all large clusters of any SBM instance. Their algorithm on a graph of n vertices retrieves
√
all clusters of size at least n with high probability. Their main result in our context is given as
follows.
13

3

23

2

Constants: N = (2 ε2)k , M = 64k
, L = (2 ε4)k
ε
Faulty-Query-k-means(X, k, ε)
UncoveredCluster(C, S, J)
(1) J ← ∅
- For all i ∈ {1, ..., k}: Si ← ∅
(2) C ← ∅
-i←1
(3) for i = 1 to k
- For all y ∈ J: {Si ← y; i++}
(3.1) D2 -sample a multi-set S of N points
- T1 , . . . , Tl = PartitionSample(S) for l < k
from X with respect to center set C
- for j = 1, . . . , l
(3.2) s ← UncoveredCluster(C, S, J)
- if IsCovered(C, Tj ) is FALSE
(3.3) T ← UniformSample(X, C, s)
- if ∃t such that St = ∅, then St = Tj
(3.4) If (|T |< M ) continue
- Let Si be the largest set such that i > |J|
(3.5) J ← J ∪ {s}
- Let s ∈ Si be the element with smallest
(3.6) C ← C ∪ µ(T )
value of Φ(C, {s}) in Si
(4) return(C)
- return(s)
UniformSample(X, C, s)
-S←∅
- For i = 1 to L:
PartitionSample(S)
- D2 -sample point x ∈ X with respect to center set C - Construct SBM instance I by querying OE (s, t) ∀s, t ∈ S
- U = U ∪ {x}
- Run cluster recovery algorithm of Ailon et al. [ACX15] on I
- T1 , . . . , Tl = PartitionSample(U ) for l < k
- Return T1 , . . . , Tl for l < k
- for j = 1, . . . , l
- If (IsCovered(s, Tj ) is TRUE)


- ∀x ∈ Tj , with probability
in multi-set S
- return (S)

ε
128

·

Φ(C,{s})
Φ(C,{x})

add x IsCovered(C,U)
- for c ∈ C
– if for majority of u ∈ U , OE (c, u) = 1, Return TRUE
- Return FALSE

Table 3. Approximation algorithm for k-means (top-left frame) using faulty oracle. Note that µ(T ) denotes
the centroid of T and D2 -sampling w.r.t. empty center set C means just uniform sampling. The algorithm
UniformSample(X, C, s) (bottom-left) returns a uniform sample of size Ω(1/ε) (w.h.p.) from the optimal cluster
in which point s belongs.

Lemma 21 ([ACX15]). There exists a polynomial time algorithm that, given an instance of a
√
stochastic block model on n vertices, retrieves all clusters of size at least Ω( n) with high probability,
provided q < 1/2.
We use Lemma 21 to retrieve the large clusters from our SBM instance I. We also need to make
sure that the sample S is such that its overlap with at least one uncovered optimal cluster is large,
where an optimal cluster Sj for some j is uncovered
if C ∩ Sj = ∅. More formally, we would require
p
the following: ∃j ∈ [k] such that |Sj |≥ Ω( |S|), and Xj is uncovered by C. From Corollary 1,
given a set of centers C with |C|< k, there exists an uncovered cluster such that any point sampled
ε
using D 2 -sampling would belong to that uncovered cluster with probability at least 4k
. Therefore,
ε
2
in expectation, D -sample S would contain at least 4k |S| points from one such uncovered optimal
p
2
cluster. In order to ensure that this quantity is at least as large as |S|, we need |S|= Ω( 16k
ε2 ).
Our bounds for N and L, in the algorithm, for the size of D 2 -sample S satisfy this requirement
with high probability. This follows from a simple application of Chernoff bounds.
12 2

Lemma 22. For D 2 -sample S of size at least 2 ε2k , there is at least one partition Sj = S ∩ Xj
among the partitions returned by the sub-routine PartitionSample corresponding to an uncovered
1
cluster Xj with probability at least (1 − 16k
).
Proof. From Corollary 1, for any point p sampled using D 2 -sampling, the probability that point p
ε
. In expectation, the number of points sampled
belongs to some uncovered cluster Xj is at least 4k
10
ε|S|
2 k
from uncovered cluster Xj is E[|Sj |] = 4k = ε . Exact recovery using Lemma 21 requires |Sj | to
6
1
be at least 2 εk . Using Chernoff bounds, the probability of this event is at least (1 − 16k
).
⊔
⊓
Following Lemma 22, we condition on the event that there is at least one partition corresponding
to an uncovered cluster among the partitions returned by the sub-routine PartitionSample. Next,
we figure out using the sub-routine IsCovered which of the partitions returned by PartitionSample
are covered and which are uncovered. Let T1 , . . . , Tl be the partitions returned by PartitionSample
where l < k. Sub-routine IsCovered determines whether a cluster is covered or uncovered in the
following manner. For each j ∈ [l], we check whether Tj is covered by some c ∈ C. We query oracle
OE with pairs (v, c) for v ∈ Tj and c ∈ C. If majority of the query answers for some c ∈ C is 1, we
say cluster Tj is covered by C. If for all c ∈ C and some Tj , the majority of the query answers is
0, then we say Tj is uncovered by C. Using Chernoff bounds, we show that with high probability
uncovered clusters would be detected.
Lemma 23. With probability at least (1 −
correctly by the sub-routine IsCovered.

1
16k ),

all covered and uncovered clusters are detected

Proof. First, we figure out the probability that any partition Tj for j ∈ [l] is detected correctly
as covered or uncovered. Then we use union bound to bound the probability that all clusters
are detected correctly. Recall that each partition returned by PartitionSample has size at least
6
|Tj | ≥ 2 εk for j ∈ [l]. We first compute for one such partition Tj and some center c ∈ C, the
probability that majority of the queries OE (v, c) where v ∈ Tj are wrong. Since each query answer
is wrong independently with probability q < 1/2, in expectation the number of wrong query answers
would be q|Tj |. Using Chernoff bound, the probability that majority of the queries is wrong is at
most e−

1 2
26 k
(1− 2q
)
3ε

. The probability that the majority of the queries is wrong for at least one center
6

1 2
− 23εk (1− 2q
)

c ∈ C is at most ke

probability at least (1 −

6

. Again using union bound all clusters are detected correctly with

1 2
2 k
k2 e− 3ε (1− 2q ) )

≥ (1 −

1
16k ).

⊔
⊓

1
With probability at least (1 − 8k
), given a D 2 -sample S, we can figure out the largest uncovered optimal cluster using the sub-routines PartitionSample and IsCovered. The analysis of the
Algorithm 3 follows the analysis of Algorithm 2. For completeness, we compute the probability of
success, and the query complexity of the algorithm. Note that s in line (3.2) of the Algorithm 3
1
1
is chosen correctly with probability (1 − 4k
)(1 − 8k
). The uniform sample in line (3.3) is chosen
1
1
properly with probability (1 − 4k )(1 − 8k ). Since, given the uniform sample, success probability
1
), overall the probability of success becomes (1 − k1 ). For
using Inaba’s lemma is at least (1 − 4k
6
query complexity, we observe that PartitionSample makes O( kε8 ) same-cluster queries to oracle
4
OE , query complexity of IsCovered is O( kε4 ). Since PartitionSample is called at most k times,
7
total query complexity would be O( kε8 ). Note that these are bounds for dataset that satisfies (k, ε)irreducibility condition. For general dataset, we will use O(ε/k) as the error parameter. This causes
the number of same-cluster queries to be O(k15 /ε8 ).

6

Conclusion and Open Problems

This work explored the power of the SSAC framework defined by Ashtiani et al. [AKBD16] in the
approximation algorithms domain. We showed how same-cluster queries allowed us to convert the
popular k-means++ seeding algorithm into an algorithm that gives constant approximation for the
k-means problem instead of the O(log k) approximation guarantee of k-means++ in the absence of
such queries. Furthermore, we obtained an efficient (1+ε)-approximation algorithm for the k-means
problem within the SSAC framework. This is interesting because it is known that such an efficient
algorithm is not possible in the classical model unless P = NP.
Our results encourages us to formulate similar query models for other hard problems. If the
query model is reasonable (as is the SSAC framework for center-based clustering), then it may
be worthwhile exploring its powers and limitations as it may be another way of circumventing the
hardness of the problem. For instance, the problem closest to center-based clustering problems such
as k-means is the correlation clustering problem. The query model for this problem may be similar
to the SSAC framework. It will be interesting to see if same-cluster queries allows us to design
efficient algorithms and approximation algorithms for the correlation clustering problem for which
hardness results similar to that of k-means is known.

References
ABS12.
ABV14.
ACKS15.

ACX15.
ADK09.

AKBD16.

Pranjal Awasthi, Avrim Blum, and Or Sheffet. Center-based clustering under perturbation stability.
Information Processing Letters, 112(1):49 – 54, 2012.
Pranjal Awasthi, Maria-Florina Balcan, and Konstantin Voevodski. Local algorithms for interactive
clustering. In ICML, pages 550–558, 2014.
Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop. The Hardness
of Approximation of Euclidean k-Means. In Lars Arge and János Pach, editors, 31st International
Symposium on Computational Geometry (SoCG 2015), volume 34 of Leibniz International Proceedings
in Informatics (LIPIcs), pages 754–767, Dagstuhl, Germany, 2015. Schloss Dagstuhl–Leibniz-Zentrum
fuer Informatik.
Nir Ailon, Yudong Chen, and Huan Xu. Iterative and active graph clustering using trace norm minimization without cluster size constraints. Journal of Machine Learning Research, 16:455–490, 2015.
Ankit Aggarwal, Amit Deshpande, and Ravi Kannan. Adaptive sampling for k-means clustering. In
Irit Dinur, Klaus Jansen, Joseph Naor, and Jos Rolim, editors, Approximation, Randomization, and
Combinatorial Optimization. Algorithms and Techniques, volume 5687 of Lecture Notes in Computer
Science, pages 15–28. Springer Berlin Heidelberg, 2009.
Hassan Ashtiani, Shrinu Kushagra, and Shai Ben-David. Clustering with same-cluster queries. In NIPS.
2016.

ANFSW16. Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k-means
and euclidean k-median by primal-dual algorithms. arXiv preprint arXiv:1612.07925, 2016.
AV07.
David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding. In Proceedings
of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, SODA ’07, pages 1027–1035,
Philadelphia, PA, USA, 2007. Society for Industrial and Applied Mathematics.
BB08.
Maria-Florina Balcan and Avrim Blum. Clustering with interactive feedback. In International Conference
on Algorithmic Learning Theory, pages 316–328. Springer Berlin Heidelberg, 2008.
BBG09.
Maria-Florina Balcan, Avrim Blum, and Anupam Gupta. Approximate clustering without the approximation. In Proc. ACM-SIAM Symposium on Discrete Algorithms, pages 1068–1077, 2009.
BBM04.
Sugato Basu, Arindam Banerjee, and Raymond J. Mooney. Active semi-supervision for pairwise constrained clustering. In Proceedings of the Fourth SIAM International Conference on Data Mining, Lake
Buena Vista, Florida, USA, April 22-24, 2004, pages 333–344, 2004.
BJA16.
Anup Bhattacharya, Ragesh Jaiswal, and Nir Ailon. Tight lower bound instances for k-means++ in two
dimensions. Theor. Comput. Sci., 634(C):55–66, June 2016.
BR13.
Tobias Brunsch and Heiko Rglin. A bad instance for k-means++. Theoretical Computer Science, 505:19
– 26, 2013.
CAKM16. Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu. Local search yields approximation schemes
for k-means and k-median in euclidean and minor-free metrics. 2016 IEEE 57th Annual Symposium on
Foundations of Computer Science (FOCS), 00:353–364, 2016.
Das08.
Sanjoy Dasgupta. The hardness of k-means clustering. Technical Report CS2008-0916, Department of
Computer Science and Engineering, University of California San Diego, 2008.
Din07.
Irit Dinur. The pcp theorem by gap amplification. J. ACM, 54(3), June 2007.
FMS07.
Dan Feldman, Morteza Monemizadeh, and Christian Sohler. A PTAS for k-means clustering based on
weak coresets. In Proceedings of the twenty-third annual symposium on Computational geometry, SCG
’07, pages 11–18, New York, NY, USA, 2007. ACM.
FRS16.
Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour. Local search yields a PTAS for
k-means in doubling metrics. 2016 IEEE 57th Annual Symposium on Foundations of Computer Science
(FOCS), 00:365–374, 2016.
IKI94.
Mary Inaba, Naoki Katoh, and Hiroshi Imai. Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering: (extended abstract). In Proceedings of the tenth annual symposium
on Computational geometry, SCG ’94, pages 332–339, New York, NY, USA, 1994. ACM.
IP01.
Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of Computer and
System Sciences, 62(2):367 – 375, 2001.
IPZ01.
Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential
complexity? Journal of Computer and System Sciences, 63(4):512 – 530, 2001.
JKS14.
Ragesh Jaiswal, Amit Kumar, and Sandeep Sen. A simple D2 -sampling based PTAS for k-means and
other clustering problems. Algorithmica, 70(1):22–46, 2014.
JKY15.
Ragesh Jaiswal, Mehul Kumar, and Pulkit Yadav. Improved analysis of D2 -sampling based PTAS for
k-means and other clustering problems. Information Processing Letters, 115(2):100 – 103, 2015.
KSS10.
Amit Kumar, Yogish Sabharwal, and Sandeep Sen. Linear-time approximation schemes for clustering
problems in any dimensions. J. ACM, 57(2):5:1–5:32, February 2010.
LSW17.
Euiwoong Lee, Melanie Schmidt, and John Wright. Improved and simplified inapproximability for kmeans. Information Processing Letters, 120:40 – 43, 2017.
Man16.
Pasin Manurangsi. Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph. CoRR,
abs/1611.05991, 2016.
MNV12.
Meena Mahajan, Prajakta Nimbhorkar, and Kasturi Varadarajan. The planar k-means problem is NPhard. Theor. Comput. Sci., 442:13–21, July 2012.
ORSS13.
Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, and Chaitanya Swamy. The effectiveness of
lloyd-type methods for the k-means problem. J. ACM, 59(6):28:1–28:22, January 2013.
Tre04.
Luca Trevisan. Inapproximability of combinatorial optimization problems. CoRR, cs.CC/0409043, 2004.
Vat09.
Andrea Vattani. The hardness of k-means clustering in the plane. Technical report, Department of
Computer Science and Engineering, University of California San Diego, 2009.
VBR+ 14.
Konstantin Voevodski, Maria-Florina Balcan, Heiko Röglin, Shang-Hua Teng, and Yu Xia. Efficient
clustering with limited distance information. CoRR, abs/1408.2045, 2014.
VD16.
Sharad Vikram and Sanjoy Dasgupta. Interactive bayesian hierarchical clustering. In Proceedings of
the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June
19-24, 2016, pages 2081–2090, 2016.

