Deterministic $k$-Median Clustering in Near-Optimal Time

We make progress in answering Question 1 by giving a deterministic algorithm with near-optimal running time and an improved approximation of $O(\log (n/k))$, proving the following theorem.

We obtain our algorithm by adapting the “hierarchical partitioning” approach of Guha et al. [20]. We show that a modified version of this hierarchy can be implemented efficiently by using “restricted $k$-clustering” algorithms – a notation that was recently introduced by Bhattacharya et al. to design fast dynamic clustering algorithms [7]. We design a deterministic algorithm for restricted $k$-median based on the reverse greedy algorithm of Chrobak et al. [13] and combine it with the hierarchical partitioning framework to construct our algorithm.

In addition to our algorithm, we also provide a lower bound on the approximation ratio of any deterministic algorithm with a running time of $\tilde{O}(nk)$, proving the following theorem.

This lower bound establishes a separation between the randomized and deterministic settings for $k$-median – ruling out the possibility of a deterministic $O(1)$-approximation algorithm that runs in near-optimal $\tilde{O}(nk)$ time for $k=n^{o(1)}$. For example, when $k=poly(\log n)$, Theorem 2 shows that any deterministic algorithm with a near-optimal running time must have an approximation ratio of $\mathrm{\Omega }(\log n/\log \log n)$. On the other hand, Theorem 1 gives such an algorithm with an approximation ratio of $O(\log n)$, which matches the lower bound up to a lower order $O(\log \log n)$ term.

We prove Theorem 2 by adapting a lower bound on the query complexity of dynamic $k$-center given by Bateni et al. [5], where the query complexity of an algorithm is the number of queries that it makes to the distance function $d(\cdot ,\cdot )$. Our lower bound holds for any deterministic algorithm with a query complexity of $\tilde{O}(nk)$. Since the query complexity of an algorithm is a lower bound on its running time, this gives us Theorem 2. In general, establishing a gap between the deterministic and randomized query complexity of a problem is an interesting research direction [29]. Our lower bound implies such a gap for $k$-median when $k$ is sufficiently small.

For the special case of $1$-median, Chang showed that, for any constant $ϵ>0$, any deterministic algorithm with a running time of $O(n^{1+ϵ})$ has an approximation ratio of $\mathrm{\Omega }(1/ϵ)$ [10]. The lower bound for $1$-median by [10] uses very similar techniques to the lower bounds of Bateni et al. [5], which we adapt to obtain our result. In the full version of the paper [16], we provide a generalization of the lower bound in Theorem 12, giving a similar tradeoff between running time and approximation.

Two other well-studied metric $k$-clustering problems are $k$-means and $k$-center. For $k$-means, the current state-of-the-art is the same as for $k$-median. Using randomization, it is known how to obtain an $O(1)$-approximation in $\tilde{O}(nk)$ time [28]. The deterministic algorithm of [20] can be generalized to work for $k$-means as well as $k$-median (see Appendix A in the full version of the paper [16], where we describe this generalization). In particular, we can also obtain a $poly(\log (n/k))$-approximation for $k$-means in near-optimal $\tilde{O}(nk)$ time. On the other hand, for $k$-center, the situation is quite different. The classic greedy algorithm given by Gonzalez [19] is deterministic and returns a $2$-approximation in $O(nk)$ time. It is known that any non-trivial approximation algorithm must run in $\mathrm{\Omega }(nk)$ time [5], and it is NP-Hard to obtain a $(2-ϵ)$-approximation for any constant $ϵ>0$ [25]. Thus, this algorithm has an exactly optimal approximation ratio and running time.

Another related line of work considers the specific case of Euclidean spaces. It was recently shown how to obtain a $poly(1/ϵ)$-approximation in $\tilde{O}(n^{1+ϵ+o(1)})$ time in such spaces [18]. They obtain their result by adapting the $\tilde{O}(n^2)$ time deterministic algorithm of [27] using locality-sensitive hashing.

The $k$-median problem has also recently received much attention in the dynamic setting, where points in the metric space are inserted and deleted over time and the objective is to maintain a good solution. A long line of work [14, 23, 8, 17, 7, 6] recently led to a fully dynamic $k$-median algorithm with $O(1)$-approximation and $\tilde{O}(k)$ update time against adaptive adversaries, giving near-optimal update time and approximation.²²2Note that, since we cannot obtain a running time of $o(nk)$ in the static setting, we cannot obtain an update time of $o(k)$ in the dynamic setting.

In Section 2, we give the preliminaries and describe the notation used throughout the paper. In Section 3, we give a technical overview of our results. We present our algorithm in Sections 4 and 5. We defer the proof of our lower bound to the full version of the paper [16]. In Section 6, we describe our results for the $k$-means problem.

Guha et al. [20] showed how to combine an $\tilde{O}(n^2)$ time $k$-median algorithm with a simple hierarchical partitioning procedure in order to produce a faster algorithm – while incurring some loss in the approximation. Their approach is based on the following divide-and-conquer procedure:

1. 1.

   Partition the metric space $(V,w,d)$ into $q$ metric subspaces $(V_1,w,d),\mathrm{\dots },(V_q,w,d)$.

2. 2.

   Solve the $k$-median problem on each subspace $(V_i,w,d)$ to obtain a solution $S_i\subseteq V_i$.

3. 3.

   Combine the solutions $S_1,\mathrm{\dots },S_q$ to get a solution $S$ for the original space $(V,w,d)$.

The main challenge in this framework is implementing Step 3 – finding a good way to merge the solutions from the subspaces into a solution for the original space. To implement this step, they prove the following lemma, which, at a high level, shows how to use the solutions $S_i$ to construct a sparsifier for the metric space $(V,w,d)$ that is much smaller than the size of the space.

Using Lemma 5, we can compute a (weighted) subspace $(V^{\prime },w^{\prime },d)$ that has size only ${\sum }_i|S_i|=O(kq)$. Crucially, we have the guarantee that any good solution that we find within this subspace is also a good solution in the space $(V,w,d)$. Thus, we can then use the deterministic $O(1)$-approximate $\tilde{O}(n^2)$ time $k$-median algorithm of [27] to compute a solution $S$ for $(V^{\prime },w^{\prime },d)$ in $\tilde{O}(k^2{q}^2)$ time.

While the sparsification technique that is described in Lemma 5 allows us to obtain much faster algorithms by sparsifying our input in a hierarchical manner, this approach has one major drawback. Namely, the fact that sparsifying the input in this manner also leads to an approximation ratio that scales exponentially with the number of levels in the hierarchy. Unfortunately, this exponential growth seems unavoidable with this approach. This leads us to the following question.

Very recently, Bhattacharya et al. introduced the notion of “restricted $k$-clustering” in order to design efficient and consistent dynamic clustering algorithms [7]. The restricted $k$-median problem on the space $(V,w,d)$ is the same as the $k$-median problem, except that we are also given a subset $X\subseteq V$ and have the additional restriction that our solution $S$ must be a subset of $X$. Crucially, even though the algorithm can only place centers in the solution $S$ within $X$, it receives the entire space $V$ as input and computes the cost of the solution $S$ w.r.t. the entire space.

The restricted $k$-median problem allows us to take a different approach toward implementing Step 3 of the divide-and-conquer framework. Instead of compressing the entire space $(V,w,d)$ into only $O(kq)$ many weighted points, we restrict the output of the solution $S$ to these $O(kq)$ points but still consider the rest of the space while computing the cost of the set $S$. This can be seen as a less aggressive way of sparsifying the metric space, where we lose less information. It turns out that this approach allows us to produce solutions of higher quality, where the approximation scales linearly in the number of levels in the hierarchy instead of exponentially.

Efficiently implementing this new hierarchy is challenging since we need to design a fast deterministic algorithm for restricted $k$-median with the appropriate approximation guarantees. To illustrate our approach while avoiding this challenge, we first describe a simple version of our algorithm with improved approximation and near-optimal query complexity. We later show how to design such a restricted algorithm, allowing us to implement this algorithm efficiently.

Let $(V,w,d)$ be a metric space of size $n$ and $k\le n$ be an integer. We define the value $\mathrm{\ell }:={\log }_2(n/k)$, which we use to describe our algorithm. Our algorithm works in the following 2 phases.

In order to establish the approximation guarantees of our algorithm in Section 3.4, we use the fact that, given a metric subspace $(V,w,d)$ of size $n$ and a subset $X\subseteq V$, we can find a solution $S\subseteq X$ to the $k$-median problem such that

We use this fact in the proof of Claim 9 (see Equation 1), which is the key claim in our analysis of our algorithm. Furthermore, to establish the query complexity bound of our algorithm, we use the fact that we can find such a solution $S_X$ with $O(n|X|)$ many queries. To implement this algorithm efficiently, we need to be able to find such a solution in $\tilde{O}(n|X|)$ time. While designing an algorithm with these exact guarantees seems challenging (since it would require efficiently matching the bounds implied by the projection lemma), we can give an algorithm with the following relaxed guarantees, which suffice for our applications.

To prove Lemma 10, we give a simple modification of the reverse greedy algorithm of Chrobak, Kenyon, and Young [13]. The reverse greedy algorithm initially creates a solution $S\leftarrow V$ consisting of the entire space, and proceeds to repeatedly peel off the point in $S$ whose removal leads to the smallest increase in the cost of $S$ until only $k$ points remain. Chrobak et al. showed that this algorithm has an approximation ratio of $O(\log n)$ and $\mathrm{\Omega }(\log n/\log \log n)$. While this large approximation ratio might seem impractical for our purposes, we can make 2 simple modifications to the algorithm and analysis in order to obtain the guarantees in Lemma 10.

1. 1.

   We start off by setting $S\leftarrow X$ instead of $S\leftarrow V$. This ensures that the output $S$ is a subset of $X$, and gives us the guarantee that $\text{cost}(S)\le \text{cost}(X)+O(\log |X|)\cdot {\text{OPT}}_k(V)$.

2. 2.

   We return the set $S$ once $|S|\le 2k$ instead of $|S|\le k$. This allows us to obtain the guarantee that $\text{cost}(S)\le \text{cost}(X)+O(\log (|X|/k))\cdot {\text{OPT}}_k(V)$.

We provide the formal proof of Lemma 10 in Section 4.

We can now make the following key observation: In our algorithm from Section 3.4, whenever we compute a solution $S_X$ to the $k$-median problem, we impose the constraint that $S_X\subseteq R$ for a set $R$ of size $R=O(k)$. Thus, if we use the algorithm from Lemma 10 to compute our solutions within the hierarchy, whenever we apply this lemma we can assume that $|X|=O(k)$. Consequently, the approximation guarantee that we get from Lemma 10 becomes

matching the required guarantee from Equation 4.

We also prove the following lower bound for deterministic $k$-median. Due to space constraints, we defer the proof of this lower bound to the full version of the paper [16].

We prove this lower bound by adapting a lower bound construction by Bateni et al. [5]. In this paper, the authors provide a lower bound for dynamic $k$-center clustering against adaptive adversaries. Although their primary focus is $k$-center, their lower bounds can be extended to various $k$-clustering problems. The main idea is to design an adaptive adversary that controls the underlying metric space as well as the points being inserted and deleted from the metric space. Whenever the algorithm queries the distance between any two points $x,y$, the adversary returns a value $d(x,y)$ which is consistent with the distances reported for all previously queried pairs of points. Note that if we have the distances between some points (not necessarily all of them), we might be able to embed different metrics on the current space that are consistent with the queried distances. More specifically, [5] introduces two different consistent metrics, and shows that the algorithm can not distinguish between these metrics, leading to a large approximation ratio.

We use the same technique as described above with slight modifications. The first difference is that [5] considers the problem in the fully dynamic setting, whereas our focus is on the static setting. The adversary has two advantages in the fully dynamic setting:

1. 1.

   The adversary has the option to delete a (problematic) point from the space.

2. 2.

   The approximation ratio of the algorithm is defined as the maximum approximation ratio throughout the entire stream of updates.

Both of these advantages are exploited in the framework of [5]: The adversary removes any “problematic” point $x$ and the approximation ratio of the algorithm is proven to be large only in special steps (referred to as “clean operations”) where the adversary has removed all of the problematic points. In the static setting, the adversary does not have these advantages, and the approximation ratio of the algorithm is only considered at the very end.

Due to the differences between the objective functions of the $k$-median and $k$-center problems, we observed that we can adapt the above framework for deterministic static $k$-median. One of the technical points here is to show that, if we have a problematic point $x$ that is contained in the output $S$ of the algorithm, we can construct the metric so that the cost of the cluster of $x$ in solution $S$ become large. The final metric space is similar to the “uniform” metric introduced in [5] with a small modification. Since the algorithm is deterministic, the output is the same set $S$ if we run the algorithm on this final metric again. Hence, we get our lower bounds for any deterministic algorithm for the static $k$-median problem. Please see the full version of the paper for a complete proof of our lower bound [16].

Let $(V,w,d)$ be a metric space of size $n$, $X\subseteq V$ and $k^{\prime }\le |X|$ be an integer. The restricted reverse greedy algorithm ${\text{Res-Greedy}}_{k^{\prime }}$ begins by initializing a set $S\leftarrow X$ and does the following:

While $|S|>k^{\prime }$, identify the center $y\in S$ whose removal from $S$ causes the smallest increase in the cost of the solution $S$ (i.e. the point $y=\arg {\min }_{z\in S}\text{cost}(S-z)$) and remove $y$ from $S$. Once $|S|\le k^{\prime }$, return the set $S$.

Let $m$ denote the size of $X$ and let $k\le k^{\prime }$. Now, suppose that we run ${\text{Res-Greedy}}_{k^{\prime }}$ and consider the state of the set $S$ throughout the run of the algorithm. Since points are only removed from $S$, this gives us a sequence of nested subsets $S_{k^{\prime }}\subseteq \mathrm{\cdots }\subseteq S_m$, where $|S_i|=i$ for each $i\in [k^{\prime },m]$. Note that $S_{k^{\prime }}$ is the final output of our algorithm. The following lemma is the main technical lemma in the analysis of this algorithm.

Using Lemma 14, we can now prove the desired approximation guarantee of our algorithm. By using a telescoping sum, we can express the cost of the solution $S_{k^{\prime }}$ as

Applying Lemma 14, we can upper bound the sum on the RHS of Equation 5 by

Combining Equations 5 and 4.2, we get that

giving us the desired bound in Theorem 13, since $S_m=X$ and $m=|X|$.

The following analysis is the same as the analysis given in [13], with some minor changes to accommodate the fact that we are using the algorithm for the restricted $k$-median problem and to allow us to obtain an improved approximation for $k^{\prime }\ge (1+\mathrm{\Omega }(1))k$, at the cost of outputting bicriteria approximations.

We begin with the following claim, which we use later on in the analysis.

Now we describe how to implement the algorithm to run in $\tilde{O}(n|X|)$ time. In particular, we prove the following lemma.

We now show how to implement Res-Greedy to run in time $O(n|X|\log n)$. Our implementation uses similar data structures to the randomized local search in [7]. For each $x\in V$, we initialize a list $L_x$ which contains all of the points $y\in X$, sorted in increasing order according to the distances $d(x,y)$. We denote the $i^{th}$ point in the list $L_x$ by $L_x(i)$. We maintain the invariant that, at each point in time, each of the lists in $ℒ={\{L_x\}}_{x\in V}$ contains exactly the points in $S$. Thus, at each point in time, we have that $\text{cost}(S)={\sum }_{x\in V}w(x)d(x,L_x(1))$. By implementing each of these lists using a balanced binary tree, we can initialize them in $O(n|X|\log n)$ time and update them in $O(n\log n)$ time after each removal of a point from $S$. Since the $S$ initially has size $|X|$, the total time spent updating the lists is $O(n|X|\log n)$. We also explicitly maintain the clustering $𝒞={\{C_S(y)\}}_{y\in S}$ induced by the lists $ℒ$, where $C_S(y):=\{x\in V\mid L_x(1)=y\}$. We can initialize these clusters in $O(n)$ time given the collection of lists $ℒ$ and update them each time a list in $ℒ$ is updated while only incurring a $O(1)$ factor overhead in the running time. We now show that, using these data structures, we can implement each iteration of the greedy algorithm in $O(n)$ time. Since the algorithm runs for at most $|X|$ iterations, this gives us the desired running time.

Let $(V,w,d)$ be a metric space of size $n$ and $k\le n$ be an integer. We also define the value $\mathrm{\ell }:=\lceil {\log }_2(n/k)\rceil$, which we use to describe our algorithm. Our algorithm works in 3 phases, which we describe below.

We now analyze our algorithm by bounding its approximation ratio and running time.