Faster Randomized and Deterministic \(k\)-Clustering on Graphs
July 08, 2026
Abstract
In this paper, we study the \((k, z)\)-clustering and \(k\)-center problems on graphs, where \((k, z)\)-clustering generalizes the \(k\)-median (\(z = 1\)) and \(k\)-means (\(z = 2\)) problems. In this work, we obtain the following main results:
Our first contribution is the first deterministic algorithm for \(k\)-center on graphs that achieves a \((2 + \varepsilon)\)-approximation in \(\tilde{O}(m)\) time. This affirmatively resolves an open problem raised by Abboud, Cohen-Addad, Lee, and Manurangsi [1]. Our techniques also extend to the \(k\)-center with outliers problem, where up to \(t\) points may be discarded.
Our second contribution is a randomized algorithm for \((k,z)\)-clustering on graphs that achieves an \(O(1)\)-approximation in \(\tilde{O}(m)\) time, which in particular covers \(k\)-median (\(z = 1\)) and \(k\)-means (\(z = 2\)). Prior to this work, an \(\tilde{O}(m)\)-time randomized algorithm was known for \(k\)-median by Thorup [2]. Moreover, a recent work of Jiang, Jin, Lou, and Lu [3] achieves \(\tilde{O}(m^{1+o(1)})\) time for general \(z\) via local search.
Finally, we design a deterministic algorithm for \((k,z)\)-clustering on graphs that achieves a \(O(\mathsf{poly}(c))\)-approximation in \(\tilde{O}(m^{1+1/c})\) time, for a positive parameter \(c\). To obtain this result, we use techniques from the Thorup–Zwick distance oracle [4]. This technical connection may be of independent interest, considering the wide application of [4] in various computational settings.
We emphasize that most of our algorithms are incremental in the sense that for any given parameter \(k\), they return a sequence of centers such that any prefix of length \(\ell \leq k\) yields an \(\ell\)-clustering solution with a constant-factor approximation.
1 Introduction↩︎
Clustering is a fundamental task in data mining and unsupervised learning with numerous applications across various domains [5]–[8]. Intuitively speaking, the goal of a clustering algorithm is to group the input data together, in structures called “clusters”, such that similar data points are contained in the same cluster.
A very popular, and arguably also very intuitive, clustering paradigm is partitional clustering in which the clusters are represented by a set of centers of a prespecified size \(k\) and each point in the data set is assigned to the cluster of its closest center. The quality of a solution is measured based on an objective on the distances of points to their closest center.
Formally, this type of \(k\)-clustering can be formulated as an optimization problem in which, for a given metric space \(\mathcal{M} = (P, \operatorname{dist})\) and a given integer \(k \geq 1\), the goal is to find a set of centers \(C \subseteq P\) with \(|C| = k\) minimizing one of the following objective functions \(f_\mathcal{M}\).
\(k\)-center objective: \(f_\mathcal{M} (C) = \max_{p \in P} \operatorname{dist}(p, C)\), where \(\operatorname{dist}(p, C) = \min_{q \in C} \operatorname{dist}(p, q)\). Here, the goal is to minimize the maximum distance of any point to its closest center.
\((k, z)\)-clustering objective: \(f_\mathcal{M} (C) = \sum_{p \in P} \operatorname{dist}(p, C)^z\) for a given constant \(z \geq 1\), where \(\operatorname{dist}(p, C) = \min_{q \in C} \operatorname{dist}(p, q)\). Here, the goal is to minimize the sum of the distances from each point to its nearest center, each raised to the power \(z\). For \(z = 1\) this is known as the \(k\)-median objective, and for \(z = 2\) this is known as the \(k\)-means objective.
Clustering under these objectives is an NP-hard problem [9] and therefore research has mainly focused on efficient approximation algorithms. There are two main algorithmic research directions:
Obtaining polynomial-time algorithms with the smallest possible approximation ratio [10]–[27].
Obtaining constant-factor approximation algorithms with the smallest possible running time [28]–[34].
In the latter direction, most notably, algorithms with running time \(\tilde{O} (k n)\) have been developed [31], [32], [35], [36] (assuming constant-time query access to distances between points of the metric space). This matches (up to polylogarithmic factors) distance-query lower bounds of \(\tilde{\Omega} (k n)\) [29], [31], [37] in this setting.
Some of these algorithms solve a variant of the problem known as incremental5 \(k\)-clustering [17], [38], in which the goal is to output a sequence \(c_1, \ldots, c_k\) of centers such that, for every \(1 \leq \ell \leq k\), the subset \(c_1, \ldots, c_\ell\) is an (approximate) \(\ell\)-clustering solution. Incremental clustering gives an efficiency gain in uncertain situations where only an upper bound on the desired number of clusters is known and the results for smaller values can instantly be retrieved without running the algorithm from scratch each time.
To obtain faster running times beyond the \(kn\) barrier, researchers have studied \(k\)-clustering in metric spaces with more structure. Two such examples are Euclidean spaces [3], [39]–[41] (with the Euclidean distance between points) and graphs of low-enough density [1]–[3], [41] (with the induced shortest-path distance between vertices). In this paper, we focus on the setting in which the metric is a graph. This is motivated by network structures such as road networks, computer networks, or social networks, which appear naturally in many contexts where clustering is employed to identify structures like communities. Furthermore, techniques for turning metric input data into a graph [42] are sometimes employed to make large amounts of data amenable to analysis. This paradigm, in the form of first computing a sparse Euclidean spanner [43]–[46] and then running a graph algorithm on the spanner, has recently also been applied to obtain the best theoretical guarantees for Euclidean \((k, z)\)-clustering in a certain regime [3]. In any case, the input to the algorithm is often a massive sparse graph, and even moderately super-linear running times in the number of edges \(m\) are quite prohibitive. Thus, it is natural to seek algorithms that are as close as possible to a linear (in number of edges) running time.
While this linear-time “gold standard” has been approached for the \(k\)-clustering objectives mentioned above [1]–[3], [41], there are still gaps concerning (a) how close we can get to linear time and (b) deterministic algorithms achieving such fast running times. The goal of this work is therefore to narrow these gaps in approaching linear running time for variants of \(k\)-clustering problems on graphs.
On the technical side, our contribution is to utilize ideas from distance approximation algorithms in graphs in the \(k\)-clustering context. In particular, we (a) employ a dynamic shortest-path approximation algorithm [47] and (b) utilize techniques from Thorup–Zwick distance oracles [4], [48], [49]. Dynamic shortest-path algorithms in general have proved to be useful in many algorithmic settings where shortest paths need to be computed repeatedly in an “outer loop” that slightly modifies the graph with each iteration (see [50] and [51] for two prominent examples in context of flows and spanner). We identify this behavior for \(k\)-center and \((k,z)\)-clustering and leverage the power of dynamic approximate shortest paths to obtain efficiency gains. For the \((k, z)\)-clustering problem, we utilize the data structures used in the distance oracle construction of Thorup and Zwick [4], [48], [49]. By adapting these structures, we can replace a randomized method of estimating sizes of balls (up to a certain radius) around each node [52] by a deterministic one with mild overheads.
1.1 Our Results and the State of the Art↩︎
The following characterization of running-time statements will facilitate the discussion of our and prior work. We say that the worst-case running time \(T (n, m)\) of a given algorithm on any graph with \(n\) nodes and \(m\) edges is:
Nearly-linear, if \(T (n, m) = O (m \cdot (\log n)^c)\) for some constant \(c\) (“polylogarithmic overhead”).
Almost-linear, if \(T (n, m) = O (m^{1+o(1)})\) (“subpolynomial overhead”).
Close-to-linear, if \(T (n, m) = O (m^{1+\mu})\) for any constant \(\mu > 0\) (“arbitrarily-small-polynomial overhead”).
In the following, we outline our results and how they compare to the state of the art. A quick overview is also summarized in Table ¿tbl:tab:results?.
6pt
lllll Problem & Approx. & Running time & Det./Rand. & Reference
& \(2\) & \(\Tilde{O}(m)\) & Rand. & [2]
& \(2+\varepsilon\) & \(\Tilde{O}(m/\log(\varepsilon))\) & Rand. & [1]
& \(2+\varepsilon\) & \(\tilde{O}(m/\varepsilon)\) & Det. & [lem:deterministic95k95center95gon]
& \(3^{\ddagger}\;\) & \(\mathrm{poly}(n)\) & Det. & [53]
& \(2^{\dagger}\) & \(\mathrm{poly}(n)\) & Rand. & [54]
& \(2+\varepsilon ^{\dagger}\) & \(\tilde{O}(m/\varepsilon)\) & Rand. & [lem:outlier-2approx]
& \((2,\,O(1/\varepsilon))^{*}\) & \(\mathrm{poly}(n)\) & Rand. & [54]
& \((2+\varepsilon, O(1/\varepsilon))^{*}\) & \(\tilde{O}(\frac{m}{\varepsilon})\) & Rand. & [lem:outlier-bicriteria]
\(k\)-median (\(z = 1\)) & \(\mathrm{O}(1)\) & \(\tilde O (m)\) & Rand. & [2]
& \(\mathrm{O}(c^6)\) & \(\Tilde{O}(m^{1+\frac{1}{c}})\) & Rand. & [41]
& \(\mathrm{O}(1)\) & \(\Tilde{O}(m^{1+o(1)})\) & Rand. & [3]
& \(O(1)\) & \(\tilde{O}(m)\) & Rand. & [thm:randomizedkzclustering]
& \(O(\text{poly(c)})\) & \(\Tilde{O}(mn^{\frac{1}{c} } + \frac{m}{\varepsilon})\) & Det. & [thm:deterministicclustering]
\(^\dagger\) : uses at most \(O(1+\epsilon)t\) outliers \(\ddagger\) : \(k\)
is not a constant * - These are Bi-criteria Algorithms
1.1.0.0.1 \(k\)-Center clustering problem.
A randomized nearly-linear time \(2\)-approximation algorithm for \(k\)-center on graphs has been developed by Thorup [32]. Relaxing the approximation factor to \(2 + {\varepsilon}\), Abboud, Cohen-Addad, Lee, and Manurangsi [1] have obtained (1) a slightly faster randomized nearly-linear time algorithm and (2) a randomized nearly-linear time algorithm for the incremental \(k\)-center problem.
The fastest deterministic algorithms are, to the best of our knowledge, straightforward adaptations of the classic \(2\)-approximation algorithms by Gonzalez [35] or Hochbaum and Shmoys [36], which run in time \(\tilde{O} (k m)\). The former also solves the incremental \(k\)-center problem. In addition, following an observation by Thorup [32], a deterministic incremental constant-factor approximation algorithm for \(k\)-center clustering with running time \(\tilde{O} (n^2)\) can be obtained by first running the approximate all-pairs shortest paths algorithm of Cohen and Zwick [55] and then running Gonzalez’s algorithm [35] with the precomputed approximate distances. Designing a deterministic nearly-linear time \(k\)-center algorithm was explicitly stated as an open problem by Abboud et al. [1].
We resolve this open problem and provide a \((2 + {\varepsilon})\)-approximation algorithm that also works for the incremental version. More formally, we obtain the following theorem, which we prove in 3.
thmkcenter There is a deterministic algorithm for the incremental \(k\)-center problem that, given a weighted undirected graph \(G = (V,E,w)\), an integer \(k \geq 1\), and an accuracy parameter \(0 < \varepsilon \leq 1\), computes a \((2 + {\varepsilon})\)-approximate solution in time \(\tilde{O}(\frac{m}{\varepsilon})\).
László Kozma [56] proved that no incremental \(k\)-center algorithm, regardless of its running time, has approximation ratio strictly below \(2\) on every prefix, already on weighted path graphs. Hence [lem:deterministic95k95center95gon] is optimal for incremental algorithms up to the additive \(\varepsilon\).
An interesting variant of \(k\)-center providing more robustness in real-world data analysis tasks allows the algorithm to specify up to \(t\) outliers (that then are not evaluated in the objective function). For this \(k\)-center with outliers problem, previous works by Charikar et al. [53] and Ding et al (only for constant \(k\) and having \((1+{\varepsilon})t\) outliers). [54] provided polynomial-time algorithms with approximation factors of 3 (deterministic) and 2 (randomized), respectively.
We provide a randomized nearly-linear time \((2 + {\varepsilon})\)-approximation algorithm for \(k\)-center clustering with outliers that essentially is an efficient implementation of the Ding et al.[54] approach. More formally, we obtain the following theorem that we prove in 3.
thmkcenteroutlier For constant \(k\) 6, there is a randomized algorithm for the \(k\)-center problem with at most \(t\) outliers that, given a weighted undirected graph \(G = (V,E,w)\), integer \(t \geq 0\), and an accuracy parameter \(0 < \varepsilon \leq 1\), computes with probability \((1 - t/n) \cdot \left( \frac{{\varepsilon}}{\lceil( 1+\varepsilon)\rceil} \right)^{k-1},\) a \((2 + {\varepsilon})\)-approximate solution in time \(\tilde{O}(\frac{m}{\varepsilon})\) with at most \((1+{\varepsilon})t\) outliers .
In Appendix 8, we also provide an efficient implementation of a bi-criteria approximation for \(k\)-center with outliers that achieves constant-factor approximation while allowing \(O(\frac{k}{\varepsilon})\) centers.
1.1.0.0.2 \((k, z)\)-Clustering problem.
A randomized nearly-linear time constant-factor approximation algorithm for \(k\)-median (\(z = 1\)) was developed by Thorup [32]. Recently, two independent works have addressed fast \((k, z)\)-clustering on graphs, which in particular includes solutions for \(k\)-median (\(z = 1\)) and \(k\)-means (\(z = 2\)). First, Jiang, Jin, Lou, and Lu [3] have presented a randomized almost-linear time algorithm for \((k, z)\)-clustering with constant-factor approximation. Second, Dupré la Tour and Saulpic [41] have presented a randomized close-to-linear time algorithm for incremental \((k, z)\)-clustering with constant-factor approximation. As remarked by [41], it is conceivable that Thorup’s approach may be extendable to \(k\)-means using recent results on the primal-dual method for \(k\)-means. However, Thorup’s approach does not readily extend to incremental clustering and it is arguably much more complex than the greedy framework of [41].
We generalize/subsume all of these results by providing a randomized nearly-linear time algorithm for incremental \((k, z)\)-clustering with constant-factor approximation. More formally, we obtain the following theorem that we prove in 5.
thmrandomizedkzclustering There is a randomized algorithm for the incremental7 \((k, z)\)-clustering problem that, given a weighted undirected graph \(G = (V,E,w)\), an integer \(k \geq 1\) aspect ratio \(\Delta\) 8, and a constant \(z \geq 1\), computes with high probability an \(O(1)\)-approximate solution in \(\tilde{O}(m \log(\Delta))\) time.
To the best of our knowledge, no deterministic algorithm tailored to the graph setting is known. However, again following the observation by Thorup [32], a deterministic incremental constant-factor approximation algorithm for \((k, z)\)-clustering with running time \(\tilde{O} (n^2)\) can be obtained by first running the approximate all-pairs shortest paths algorithm of Cohen and Zwick [55] and then running the metric incremental \((k, z)\)-clustering algorithm of Mettu and Plaxton [17] with the \(\rho\)-metric (obeying the triangle inequality up to a factor \(\rho = 3\)) given by the approximate shortest-path distances.
We resolve this limitation by providing the first deterministic close-to-linear time algorithm for incremental \((k, z)\)-clustering with constant-factor approximation. More formally, we obtain the following theorem, which we prove in 6.
thmdeterministicclustering There is a deterministic algorithm for the incremental \((k,z)\)-clustering problem that, given a weighted undirected graph \(G = (V,E,w)\), an integer \(k \ge 1\), an integer parameter \(t \ge 1\), a constant \(z \ge 1\), and an accuracy parameter \(0 < \varepsilon \le 1\), computes an \(O(\mathrm{poly}(t))\)-approximate solution in time \(\tilde{O}\bigl(t \cdot m \cdot n^{\frac{1}{t}} + \tfrac{m}{\varepsilon}\bigr)\).
2 Technical Overview↩︎
All of our algorithms utilize a deterministic Source-Insertion dynamic \((1+{\varepsilon})\)-SSSP (single-source shortest paths) algorithm, recently developed by Górkiewicz and Karczmarz [47]. This data structure achieves \(\tilde{O}(m)\) total update time for processing adversarial edge insertions only to the source.9 Our deterministic \(k\)-center and \(k\)-center with outlier results are mainly based on a direct application of this data structure in the Gonzalez framework [35]. Namely, we use a Source-Insertion SSSP to iteratively find the furthest vertex to the current set of centers.
Our \((k,z)\)-clustering algorithms are based on the recursive greedy algorithm by Dupré la Tour and Saulpic [41] that gives an efficient implementation of the Mettu-Plaxton [17] framework. For a vertex \(v \in V\) and radius \(r \ge 0\), the ball of radius \(r\) around \(v\) is defined as \(B({v},{r}) := \{ u \in V \mid \operatorname{dist}(v,u) \le r \}.\) At a high level, the framework iteratively uses two main primitives:
Ball-size estimation: estimating \(|B(v,\,r)|\) for specific \((v,r)\) pairs, .
Computing approximate balls: compute an approximate ball \(N(v,\,r)\) such that \(B(v,\,r)\subseteq N(v,\,r)\subseteq B(v,\,c \cdot r)\), where \(c\) is a constant.
We first explain how using the data structure of [47] implies an improved randomized result. Then we provide a more technical deterministic algorithm that uses primitives from the Thorup-Zwick distance oracles to efficiently compute and query approximate neighborhood. More specifically:
2.0.0.0.1 Randomized approach.
For the ball-size estimation primitive, similar to [41], we plug in the ball-size estimation data structure by Cohen [52]. In the recursive greedy framework, we need to repeatedly and greedily select a set of centers and approximate balls. Our novelty in ensuring that all of this iterative process can be done in nearly-linear time is the use of two shortest-path primitives.
One primitive uses a truncated Dijkstra from a set of carefully selected centers in such a way that ensures each edge is relaxed at most twice for any fixed radius \(r\). This is repeated for \(O(\log\Delta)\) radius scales, leading to \(O(m\log\Delta)\) time.
Another primitive is needed to compute approximate balls around the set of chosen centers efficiently. Recomputing the approximate balls for each selected center would be too expensive. Therefore we amortize these computations via the Source-Insertion SSSP of [47] in total linear time. In the variant of [41] for graphs, this step uses probabilistic graph decompositions from [57], which incurs an additional polynomial factor that we manage to avoid.
2.0.0.0.2 Deterministic approach.
There are two source of randomness in the algorithm of [41]: one is Cohen’s ball estimation [52], and another one is an iterative approximate balls computation. In [41], this is done via a probabilistic decomposition. We make the second primitive deterministic with the described Source-Insertion data structure and truncated Dijkstra. However, a major challenge is using the ball-size estimation. We need a new approach for making this deterministic as Cohen’s algorithm [52] is inherently randomized.
We replace this step with a deterministic ball approximation approach based on the notion of bunch and clusters used in the Thorup-Zwick distance oracle [4]. Concretely, we define \(N(v,\,r)\) as the union of the truncated bunch \(\mathrm{Bunch}(v,r)\) with the truncated clusters of \(v\)’s pivots (4 ). Here additional approximation and running time factors are added compared to our randomized construction, that depend on the balls approximation factors.
We have to be careful in how we define the approximate balls, so that each vertex overlaps with a constant number of such neighborhoods. A more naive use of Thorup-Zwick clusters results in each vertex overlapping with \(n^{1/c}\) clusters, for some constant \(c\). However, we define the neighborhoods in such a way that they overlap with \(c\) such clusters, and this is crucial for our final approximation factor.
3 Deterministic Greedy \(k\)-Center and Faster \(k\)-Center with Outlier↩︎
In this section, first, we will state the Source-Insertion SSSP 1, which will be used in the \(k\)-center 1 and also later in \((k,z)\) clustering [thm:randomizedkzclustering]. Next, we give a brief overview of Gonzalez algorithm and the modification required for our result. Lastly, we will sketch how it can be extended to \(k\)-center with outlier.
Lemma 1 (Source-Insertion SSSP [47]). Consider a parameter \(\varepsilon \in (0,1)\). Let \(G = (V, E, w)\) be a directed graph with edge weights in \(\{0\} \cup [1,W]\), and let \(s \in V\) be a source vertex. There exists a deterministic data structure that explicitly maintains distance estimates \(\delta : V \to \mathbb{R}_{\ge 0}\) satisfying \(\operatorname{dist}_G(s,v) \;\le\; \delta(v) \;\le\; (1+\varepsilon)\cdot \operatorname{dist}_G(s,v) \;\; \text{for all vertices } v \in V\).
The data structure supports only insertions (or weight decreases) of source edges \(e = sv\), with \(v \in V\). The total update time is \(O\!\left(\frac{m \log(\Delta)\,\log^2 n}{\varepsilon} + \Lambda \right)\), where \(m\) is the final number of edges in \(G\), and \(\Lambda\) is the total number of updates.
The classical greedy algorithm for \(k\)-center, due to Gonzalez [35], proceeds as follows. It starts by selecting an arbitrary vertex \(c_1 \in V\) as the first center. Let \(C_1 = \{c_1\}\). In each subsequent iteration \(i = 2, \dots, k\), the algorithm selects the vertex \(c_i\) that is farthest from the current set of centers \(C_{i-1}\): \(c_i \gets \max_{v \in V} \operatorname{dist}(v, C_{i-1}),\) and updates the set of centers as \(C_i \gets C_{i-1} \cup \{c_i\}\). This algorithm guaranties a \(2\)-approximation for the \(k\)-center problem.
Our deterministic algorithm builds on the classical Gonzalez algorithm [35], but achieves \(\tilde{O}(m)\) time complexity through careful use of Source-Insertion Single Source Shortest Path computations. The key insight is that maintaining distances from a super-source vertex connected to all selected centers allows us to efficiently identify the (approximate) farthest vertex from the current set of centers at each iteration.
Proof. Let \(G = (V,E,w)\) be a graph with nonnegative edge weights. We implement the classical Gonzalez [35] (see 1) using the \((1+\varepsilon)\)-approximate Insert-only Single Source Shortest Path data structure of 1. Let \(\hat{d}_s(\cdot)\) denote the maintained distance estimate from \(s\).
1 is implemented using the Source-Insertion SSSP data structure of 1 as follows. At each iteration \(i = 2 \ldots k\), the algorithm inserts a zero-weight edge \((s,c_i)\). This causes the Source-Insertion SSSP structure to update the distance estimates \(\operatorname{dist}(v,C_i) \le \hat{d}(v)\leq (1+\varepsilon) \operatorname{dist}(v,\{c_1,\ldots,c_i\})\) for all \(v\in V\). More formally,
Observation 1. After processing center set \(C_i = \{c_1, \ldots, c_i\}\) through the incremental SSSP data structure, the maintained distance estimates satisfy: \(\operatorname{dist}_G(v, C_i) \leq \hat{d}(v) \leq (1+\varepsilon) \cdot \operatorname{dist}_G(v, C_i) \quad \text{for all } v \in V,\) where \(\hat{d}(v)\) is the distance estimate from \(s\) to \(v\) in the augmented graph \(G'\).
To implement the \(\arg\max_{v \in V} \hat{d}_s(v)\) in Line \(7\) of the 1 at each iteration, we maintain the values \(\hat{d}_s(v)\) in a binary heap (or any other priority queue) keyed by the current distance estimate. Whenever a distance estimate decreases, we perform a corresponding decrease-key operation in the heap.
lemkcenterproof 1 produces an incremental \((2+\varepsilon)\)-approximation for the \(k\)-center problem.
Proof. Let \(C_i = \{c_1, \dots, c_i\}\) be the center set after iteration \(i\) and let \(\hat{d}_i(v)\) be the distance estimate after processing \(i\) centers. Define \(c_{k+1} \gets \arg\max_{v \in V} \hat{d}_k(v)\) as a hypothetical \((k+1)\)-th center, and let \(r = \hat{d}_k(c_{k+1})\). By 1, \(\operatorname{dist}_G(v, C) \leq \hat{d}_k(v) \leq r\) for all \(v \in V\), so it suffices to bound \(r\).
For each \(i = 2, \dots, k+1\), the algorithm chose \(c_i\) as the approximate farthest point from \(C_{i-1}\), so by 1, \(\operatorname{dist}_G(c_i, C_{i-1}) \;\geq\; \frac{\hat{d}_{i-1}(c_i)}{1+\varepsilon} \;\geq\; \frac{r}{1+\varepsilon},\) where the last inequality uses the fact that distance estimates are non-increasing as centers are added, so \(\hat{d}_{i-1}(c_i) \geq r\). In particular, all \(k+1\) points \(c_1, \dots, c_{k+1}\) are pairwise at distance greater than \(r/(1+\varepsilon)\).
Since the optimal solution has only \(k\) centers, two of the \(k+1\) points \(c_i, c_j\) must share the same optimal center. By the triangle inequality, \[\frac{r}{1+\varepsilon} \;<\; \operatorname{dist}_G(c_i, c_j) \;\leq\; 2 \cdot \mathrm{OPT}.\]
Rearranging gives \(\max_{v \in V} \operatorname{dist}_G(v, C) \leq r \leq 2(1+\varepsilon) \cdot \mathrm{OPT}\). Running the insert only SSSP structure with \(\varepsilon/2\) in place of \(\varepsilon\) yields the claimed \((2+\varepsilon)\)-approximation. The incremental property holds because for any \(i \leq k\), the sequence \(c_1, \dots, c_i\) is exactly the output of the algorithm run with parameter \(i\) instead of \(k\). The same analysis applies to show that \(C_i\) is a \((2+\varepsilon)\)-approximation compared to \(\mathrm{OPT}_i\), where \(\mathrm{OPT}_i\) denotes the optimal radius achievable with \(i\) centers.. ◻
We will use the below 2 in the proof of our running time [lem:det-gon-time].
Lemma 2 (Vertex‑touch reporting [47]). The incremental \((1+\varepsilon)\)‑approximate SSSP structure of 1 for any source‑edge insertion \((s,v)\) returns a set \(V_{\rm touched}\subseteq V\) consisting of exactly the vertices whose distance estimate decreases because of the insertion. Moreover, over any sequence of \(\Lambda\) such insertions the total running time (and the total size of all returned sets) is \(O\!\bigl(m\log(\Delta)\log n/\varepsilon+\Lambda\bigr)=\tilde{O}(m)\) when \(\Lambda=O(n)\) and \(\varepsilon=\Theta(1)\).
lemkcentertime The running time of 1 is \(\tilde{O}(\frac{m}{\varepsilon})\)
Proof. We account for each component of the algorithm separately.
Insert only SSSP structure. Over all \(k\) iterations, exactly \(k \leq n\) zero-weight edges \((s, c_i)\) are inserted into the
augmented graph \(G'\). By 1, the Insert only SSSP structure handles the full sequence of insertions and maintains
all distance estimates in total time \(\tilde{O}(\frac{m}{\varepsilon})\).
Heap operations. Since each inserted edge has weight zero and connects \(s\) directly to a center, inserting \((s, c_i)\) can only decrease distance estimates —
never increase them. Therefore, the heap requires only decrease-key and find-max operations throughout the algorithm. The number of decrease-key operations equals the number of distance updates performed by the Insert
only SSSP structure, which is \(\tilde{O}(m)\) by 2. Each such operation costs \(O(\log
n)\), contributing \(\tilde{O}(m)\) in total. The \(k \leq n\) find-max calls, each cost \(\tilde{O}(1)\).
Both components run in at most \(\tilde{O}(\frac{m}{\varepsilon})\), hence the total running time of 1 is \(\tilde{O}(\frac{m}{\varepsilon})\). ◻
◻
Remark 2. An alternative approach constructs a maximal distance-\(d\) independent set via the same Source-Insertion SSSP structure, then binary-searches over \(d\) to achieve a \((2+\varepsilon)\)-approximation. This also runs in \(\tilde{O}(m)\) time but does not naturally yield an nested center sequence, so we prefer the Gonzalez approach here.
For the \(k\)-center with \(t\) outliers, in 1, at each iteration \(i\), we find a set \(S\) of the \((1+ \varepsilon)t\) furthest vertices from the super source and randomly select one vertex from the set \(S\) as the next center. We prove [lem:outlier-2approx] in 8.
4 Greedy \((k,z)\)-Clustering Algorithm↩︎
In this section we review the greedy \((k,z)\)-clustering algorithm of Dupré la Tour and Saulpic [41], a simplification of the algorithm of Mettu and Plaxton [17], and we present it as a template. The algorithm is stated in terms of two abstract primitives – ball values and approximate balls (1 2 below), not on how they are implemented. Both of our \((k,z)\)-clustering results are obtained by instantiating this template. In 5, we give a randomized implementation – ball values via Cohen’s ball-size estimation [52], approximate balls via truncated Dijkstra computations, and a forbidding loop driven by a single Source-Insertion SSSP structure – which yields [thm:randomizedkzclustering]. In 6, we give a deterministic implementation – ball values via the bunches and clusters of the Thorup–Zwick hierarchy [4] – which yields [thm:deterministicclustering].
The pseudo-code of this simplified greedy algorithm is provided in 2. Similarly to [41], we use a parameter \(c \geq 5\) and assume for simplicity that the aspect ratio \(\Delta\) is a power of \(2c\).
Let \(\mathcal{R} \mathrel{\vcenter{:}}= \left\{\frac{\Delta}{(2c)^\ell} \mid \ell \in \{0, \dots, \log_{2c}(\Delta) + 7\} \right\}\) be the set of radii.
4.0.0.1 The two primitives.
The template needs the graph for the following two primitives (both of which tolerate constant-factor slack).
(P1) For a parameter \(\rho \ge 1\) with \(c \ge \rho^2/2\): for every \(u \in V\) and \(r \in \mathcal{R}\), the algorithm requires a quantity \(\mathrm{Value}(B(u,r))\) satisfying \[\frac{r^z}{\rho} \cdot |B(u, r)| \;\leq\; \mathrm{Value}(B(u, r)) \;\leq\; \rho r^z \cdot |B(u, c \cdot r)|. \label{eq:value95ball}\tag{1}\]
For our randomized \((k,z)\) clustering (5), we take the value of \(\rho = 3\) and for our deterministic algorithm (6) we take \(\rho = t+1\), where \(t\) is the number of levels of the Thorup–Zwick distance oracle. The technical justification that any \(\rho \geq 1\) and \(c \geq \frac{\rho^2}{2}\) suffice is provided in 7.
(P2) Approximate balls. For every \(u \in V\) and radius \(r\), the algorithm requires a set \(N(u, r)\) satisfying \[B(u, r) \;\subseteq\; N(u, r) \;\subseteq\; B(u, c \cdot r). \label{eq:approx95ball}\tag{2}\]
This greedy algorithm maintains a set of candidate balls of various radii and it proceeds in \(k\) iterations, where \(k \geq 1\) and \(z \geq 1\) are the parameters of the \((k, z)\)-clustering instance.
In each iteration, the algorithm selects the ball with the highest “value”—a function of its radius and the number of points it contains. The center-selection loop is then performed, in which the algorithm recursively explores smaller-radius balls within the selected one to choose a precise center \(c_i\). Each vertex \(u\) in the center selection loop from which we compute \(N(u,r)\) is called candidate center. At the end of each iteration, the forbidding loop is performed, in which the algorithm removes all candidate balls that are “too close” to the newly chosen center \(c_i\). Due to the forbidding loop, the center selection loop does not run from every vertex for a specified radius \(r\). Helping us run the algorithm efficiently.
The guarantee of this greedy algorithm is that each prefix \(c_1, \ldots, c_\ell\) of the sequence of centers \(c_1, \ldots, c_\ell, \ldots, c_k\) is an \(O(1)\)-approximation for the \((\ell, z)\)-clustering problem, where \(\ell \leq k\). In order to efficiently compute each \(\mathrm{Value}(B(u, r))\), the \((k, z)\)-clustering algorithm of Dupré la Tour and Saulpic [41] employs the algorithm of Cohen [52] (see 9 in the Appendix).
5 Randomized \((k, z)\)-Clustering Algorithm on Graphs↩︎
In this section, we develop a \((k,z)\)-clustering algorithm in the graph setting that runs in \(\tilde{O}(m)\) time, as demonstrated in [thm:randomizedkzclustering].
Our \((k, z)\)-clustering algorithm is an adaptation of the algorithm by Dupré la Tour and Saulpic [41]; a pseudocode of the \((k, z)\)-clustering algorithm from [41] is provided in 2. Specifically, we improve the running time by implementing some of its components more efficiently. Consequently, we improve upon the \(\tilde{O}(m^{1+\frac{1}{c}})\)-time algorithm (for some constant \(c \geq 5\)) of Dupré la Tour and Saulpic [41], and the \(m^{1+o(1)}\)-time algorithm of Jiang, Jin, Lou, and Lu [3].
Our adapted \((k, z)\)-clustering algorithm consists of the same three components as the algorithm by Dupré la Tour and Saulpic [41] (2). These three components are: (i) the ball-value estimation, (ii) the center-selection loop, and (iii) the forbidding loop. In the following paragraphs, we describe these components alongside our improvements.
Ball-value estimation. Consider a parameter \(c \geq 5\), and let \(\mathcal{R} \mathrel{\vcenter{:}}= \left\{\frac{\Delta}{(2c)^\ell} \mid \ell \in \{0, \dots, \log_{2c}(\Delta) + 7\} \right\}\) be the set of radii considered by the algorithm. For every vertex \(u \in V\) and every radius \(r \in \mathcal{R}\), the algorithm needs access to \(\mathrm{Value}(B(u, r))\) (see 1 for the definition of \(\mathrm{Value}(\cdot)\)). In turn, \(\mathrm{Value}(\cdot)\) depends on (approximations of) the values \(b(v,\tilde{r}) \mathrel{\vcenter{:}}= |B(v,\tilde{r})|\), where \(v \in V\) is a vertex and \(\tilde{r} \in \mathcal{R}\) is a radius. These values \(b(\cdot, \cdot)\) are approximated in the preprocessing phase using the algorithm by Cohen [52]; the guarantees of Cohen’s algorithm appear in 23.
More precisely, for each pair \((u,r) \in V \times \mathcal{R}\), Cohen’s algorithm returns a \((1\pm\varepsilon)\)-approximate estimate \(\tilde{b}(u,r)\) of \(b(u,r)\) in \(O(\log\log n)\) time. Hence, the \((k, z)\)-clustering algorithm uses the approximate size \(\tilde{b}(\cdot,\cdot)\) to compute \(\mathrm{Value}(\cdot)\) for all candidate balls; this component is exactly the same as in [41].
Center-selection loop. For each candidate center \(u \in V\) and each radius \(r \in \mathcal{R}\), the approximate ball \(N(u, 10c \cdot r)\) (in Line [line:compute95N95dijkstra] of 2) is computed by running Dijkstra’s algorithm from \(u\), terminating once all vertices within distance \(10c \cdot r\) have been scanned. The pseudocode of this computation is provided in 3, where the ball \(N(u,10c \cdot r)\) is the set of all vertices extracted from \(Q_r\), \(N\) in the 3.10 Subsequently, Line [line:find95next95best95u] of 2 is performed by scanning the entire ball \(N(u, 10c \cdot r)\).
Regarding the truncated Dijkstra executions (3), for each vertex \(v \in V\) and each radius \(r \in \mathcal{R}\), the algorithm maintains a distance label \(\mathrm{d}_r[v]\), where \(\textrm{\textsf{d}}_r[v]\) is initialized to \(\infty\). For each radius \(r \in \mathcal{R}\), the algorithm maintains a priority queue \(Q_r\) that sorts the vertices based on \(\textrm{\textsf{d}}_r[\cdot]\). These data structures are reused across all center-selection loops for radius \(r\). Each execution restores both to this state before returning: it resets \(\textrm{\textsf{d}}_r[y] \gets \infty\) for exactly the vertices \(y\) it labeled (which are the vertices of its output ball \(N\), at cost \(O(|N|)\)), and \(Q_r\) becomes empty by construction . The shared data structures serve to avoid initializing an array of size \(n\) in every execution.
Forbidding loop. A single deterministic Source-Insertion SSSP algorithm is employed (from 1). In particular, a source vertex \(s\notin V\) is introduced (initially with no incident edges), and the Source-Insertion SSSP algorithm is initialized on the directed version of \(G_s = (V \cup \{s\}, E, w)\).11 Let \(\delta_s(\cdot)\) denote the maintained distance estimates from \(s\). During the forbidding loop for the \(i\)-th center \(c_i\) (where \(i \in [1, k]\)), a zero-weight edge \((s,c_i)\) is inserted into \(G_s\) and is passed to the Source-Insertion SSSP algorithm. In turn, the Source-Insertion SSSP algorithm updates the distance estimates such that (where \({\varepsilon}\in (0, 1)\)): \[\operatorname{dist}(v,\{c_1,\ldots,c_i\}) \;\le\; \delta_s(v) \;\le\; (1 + {\varepsilon})\operatorname{dist}(v,\{c_1,\ldots,c_i\})\;\; \text{for all vertices } v\in V.\] Based on 2, the Source-Insertion SSSP algorithm returns a vertex set \(V_t\), consisting of the vertices whose distance estimates decreased due to the edge \((s,c_i)\). Next, for every vertex \(v \in V_t\) and every radius \(r \in \mathcal{R}\), if \(\delta_s(v)\le (1+{\varepsilon}) 100 c^4\cdot r\) then the corresponding ball \(B(v, r)\) is removed (if not already removed) from the set of available balls \(\mathcal{B}\).
5.1 Analysis of the Randomized \((k, z)\)-Clustering Algorithm↩︎
In this section, our aim is to prove [thm:randomizedkzclustering] by analyzing the \((k, z)\)-clustering algorithm described in 5. In particular, we analyze the running time of each component and prove that each runs in \(\tilde{O}(m)\) time. The approximation ratio analysis is provided in 5.1.1, where we also show that our forbidding loop simulates that of 2.
5.1.0.1 Running Time of the Center-Selection Loop
In order to analyze the running time of all center-selection loops, we bound the total time of all truncated Dijkstra executions used to compute the balls \(N(u, 10c \cdot r)\) over all candidate centers \(u \in V\) and radii \(r \in \mathcal{R}\). We note that Lemma 3.5 in [41] (which appears as 3) is used to bound the total running time of the center-selection loops in [41].
Lemma 3 (Lemma 3.5 in [41]). For every vertex \(v \in V\) and radius \(r \in \mathcal{R}\), the ball \(B(v, r)\) appears at most once in the center-selection loop.
Since we use Truncated Dijkstra’s algorithm (see 3), our aim is to bound the number of times each edge is scanned (in 6). To achieve this, we adapt the proof of 3 from [41] to obtain 5 and then 6. Intuitively, we argue that a ball \(B(v, r)\) appears in the center-selection loop if and only if some Dijkstra execution from a candidate center \(u \in V\) with radius \(r \in \mathcal{R}\) (which computes the ball \(N(u, 10c \cdot r)\)) visits the vertex \(v\). Then based on 3 (our 5), for a fixed radius \(r \in \mathcal{R}\), each vertex \(v\) is visited by at most one truncated Dijkstra execution. In turn, each edge is scanned twice—once from each of its endpoints. The formal justification is provided in 6, and 7 follows because \(|\mathcal{R}| = O(\log \Delta)\).
The next lemma is a variation of Fact 3.4 in [41]. Essentially, it states that during the \(i\)-th center-selection loop, the candidate center chosen for radius \(r \in \mathcal{R}\) is within distance \(O(r)\) of any subsequent candidate center during the \(i\)-th center-selection loop (assuming \(c\) is a positive constant).
Lemma 4. During the \(i\)-th center-selection loop, consider the candidate center \(u_1 \in V\) for the radius \(r_1\), and let \(u_2\) be another candidate center for the radius \(r_2 \leq \frac{r_1}{2c}\). Then it holds that \(\operatorname{dist}(u_1, u_2) \leq 20c \cdot r_1\).
Proof. The proof is the same as that of Fact 3.4 in [41]. The additional observation is that in our center-selection loops, Dijkstra’s algorithm (3) computes \(B(u, 10c\cdot r)\), which is even stronger than \(B(u, 10c^2 \cdot r)\) required in the definition of the approximate ball \(N(u, 10c \cdot r)\) (for any candidate center \(u \in V\) and any radius \(r \in \mathcal{R}\)). ◻
Lemma 5. Across all center-selection loops for a fixed radius \(r \in \mathcal{R}\), each vertex \(v \in V\) is extracted from the priority queue \(Q_r\) by at most one truncated Dijkstra execution (3).
Proof. For a fixed radius \(r \in \mathcal{R}\), suppose to the contrary that a vertex \(v \in V\) is extracted from the priority queue \(Q_r\) by two truncated Dijkstra executions (3), starting from a candidate center \(u_1 \in V\) with radius \(r \in \mathcal{R}\) and from a candidate center \(u_2 \in V\) with radius \(r \in \mathcal{R}\). In other words, the vertex \(v\) is extracted from \(Q_r\) during the computation of both balls \(N(u_1, 10c \cdot r)\) and \(N(u_2, 10c \cdot r)\). Without loss of generality, assume that \(v\) is extracted from \(Q_r\) first in the execution starting from \(u_1\), and later in the execution starting from \(u_2\). The two executions belong to distinct center-selection loops, since within a single center-selection loop the radius strictly decreases. Hence we assume the loop of \(u_1\) precedes that of \(u_2\).
Let \(c_i\) be the center selected after the corresponding center-selection loop for \(u_1\), and let \(\hat{u}_2\) and \(\hat{r}\) be the initial candidate center and radius of the corresponding center-selection loop for \(u_2\); \(\hat{u}_2\) and \(\hat{r}\) are defined in Line [algline:B95init95cent95sel] of 2. The contradiction that we argue in the rest of the proof is that the ball \(B(\hat{u}_2, \hat{r})\) could not be available at the beginning of the center-selection loop for \(u_2\) (in Line [algline:B95init95cent95sel] of 2).
By the construction of 3, it holds that \(\operatorname{dist}(u_1, v)\leq 10c \cdot r\). Based on 4, we have \(\operatorname{dist}(u_1, c_i) \leq 20c \cdot r\) (note that \(c_i\) is the final candidate center of the \(i\)-th center-selection loop). Hence, by the triangle inequality it follows that: \[\operatorname{dist}(c_i, v) \;\leq\; \operatorname{dist}(c_i, u_1) + \operatorname{dist}(u_1, v) \;\leq\; 20c \cdot r + 10c \cdot r \;=\; 30c \cdot r.\] By the construction of 3, the second time that \(v\) is extracted from \(Q_r\) due to \(u_2\), it should also hold that \(\operatorname{dist}(u_2, v) \leq 10c \cdot r\). Thus, by the triangle inequality we infer that: \[\operatorname{dist}(c_i, u_2) \;\leq\; \operatorname{dist}(c_i, v) + \operatorname{dist}(v, u_2) \;\leq\; 30c \cdot r + 10c \cdot r = 40c \cdot r.\] Notice that then the ball \(B(u_2, r)\) is forbidden during the forbidding loop for \(c_i\), because \(40c \cdot r \leq 100c^4 \cdot r\).
Moreover, by 4 we have \(\operatorname{dist}(\hat{u}_2, u_2) \leq 20 c \cdot \hat{r}\), and thus \(\operatorname{dist}(c_i, \hat{u}_2) \leq \operatorname{dist}(c_i, u_2) + \operatorname{dist}(u_2, \hat{u}_2) \leq 40c \cdot r + 20 c \cdot \hat{r}\). Since \(r \leq \frac{\hat{r}}{2c}\), it follows that:12 \[\operatorname{dist}(c_i, \hat{u}_2) \;\leq\; 40c \cdot \frac{\hat{r}}{2c} + 20 c \cdot \hat{r} \;\leq\; (20 + 20c) \cdot \hat{r} \;\leq\; 40c \cdot \hat{r}.\] In turn, the ball \(B(\hat{u}_2, \hat{r})\) is forbidden during the forbidding loop for \(c_i\), because \(40c \cdot \hat{r} \leq 100c^4 \cdot \hat{r}\). This contradicts the fact that \(B(\hat{u}_2, \hat{r})\) was available at the beginning of the center-selection loop for \(u_2\). As a consequence, the vertex \(v\) cannot be extracted from the priority queue \(Q_r\) by two truncated Dijkstra executions. ◻
Lemma 6. Across all center-selection loops for a fixed radius \(r \in \mathcal{R}\), each edge \(e \in E\) is scanned at most twice.
Proof. Consider an arbitrary edge \(e = \{v_1, v_2\} \in E\) that is scanned during the truncated Dijkstra execution (3), starting from some candidate center \(u \in V\) with radius \(r \in \mathcal{R}\) (which computes the ball \(N(u, 10c \cdot r)\)). The edge \(e\) is relaxed (in Line [algline:relax95edge] of 3) only when one of its endpoints is extracted from the priority queue \(Q_r\). According to 5, for the fixed radius \(r \in \mathcal{R}\), each endpoint \(v_1\) and \(v_2\) is extracted from \(Q_r\) at most once. As a result, the edge \(e = \{v_1, v_2\}\) can be relaxed at most twice in total, as required. ◻
Lemma 7. The total running time to compute all balls \(N(u, 10c \cdot r)\) for all candidate centers \(u \in V\) and radii \(r \in \mathcal{R}\) in the center-selection loops is \(\tilde{O}(m)\).
Proof. Based on 6, across all center-selection loops for a fixed radius \(r \in \mathcal{R}\), each edge is scanned at most twice. Since \(|\mathcal{R}| = O(\log \Delta)\), each edge is scanned at most \(O(\log \Delta)\) times during all center-selection loops, concluding the claim. ◻
5.1.0.2 Running Time of the Ball-Value Estimation and the Forbidding Loop
Now we formally show the running time for computing \(\text{Value}(u,r)\) for all vertices \(u \in V\) and all radii \(r \in \mathcal{R}\) using 23 and the forbidding loop using Source-Insert SSSP.
Lemma 8. The total running time required to compute \(\text{Value}(u,r)\) for all vertices \(u \in V\) and all radii \(r \in \mathcal{R}\) is \(O(n \cdot \log \Delta \cdot \log \log n)\), in addition to the preprocessing time of 23.
Proof. Recall that \(\mathcal{R} \mathrel{\vcenter{:}}= \left\{\frac{\Delta}{(2c)^\ell} \mid \ell \in \{0, \dots, \log_{2c}(\Delta) + 7\} \right\}\), which means that \(|\mathcal{R}| = O(\log \Delta)\). Using 23, the graph can be preprocessed to build a data structure such that for each query pair \((u, r) \in V \times \mathcal{R}\), an estimate of \(|B(u,r)|\) can be returned in \(O(\log \log n)\) time. Since the total number of such queries is \(|V| \cdot |\mathcal{R}| = O(n \log \Delta)\), the claim follows. ◻
Lemma 9. The total running time to perform all forbidding loops is \(\tilde{O}(m)\).
Proof. A single deterministic Source-Insertion SSSP algorithm is employed, to which at most \(k \leq n\) zero-weight edges are passed. Based on 1, its total update time is: \[O\left(\frac{m \log(\Delta) \log^2 n}{\varepsilon} + k\right) \;=\; \tilde{O}\left(\frac{m}{\varepsilon}\right) \;=\; \tilde{O}(m).\] Furthermore based on 2, scanning the returned vertex set \(V_t\) (consisting of vertices whose distance estimates decreased due to the zero-weight edges) takes \(\tilde{O}(m)\) total time as well. ◻
5.1.1 Approximation Ratio↩︎
Our \((k, z)\)-clustering algorithm described in 5 is an adaptation of 2 by Dupré la Tour and Saulpic [41]. Since 2 yields an \(O(1)\)-approximation for the \((k,z)\)-clustering problem, it remains to justify that our \((k, z)\)-clustering algorithm outputs a constant-factor approximate solution as well. Recall that for every vertex \(u \in V\) and every radius \(r \in \mathcal{R}\), the value of the ball \(B(u, r)\) satisfies: \[\frac{r^z}{3} \cdot |B(u, r)| \;\leq\; \mathrm{Value}(B(u, r)) \;\leq\; 3 r^z \cdot |B(u, c \cdot r)|.\] Based on 23, we have \(\frac{|B(u,r)|}{1+\varepsilon} \le \tilde{b}(u,r) \le (1+ \varepsilon)|B(u,r)|\). Hence, there is no additional approximation loss in the ball-value estimation procedure compared to [41]. In the center-selection loops, exact distances are used, so there is no additional approximation loss either.
5.1.1.0.1 Forbidding loop.
In the analysis of [41], for each \(i\)-th center \(c_i \in C_k\) (where \(i \in [1, k]\)) and every radius \(r \in \mathcal{R}\), the approximate balls used in the forbidding loop of 2 satisfy: \[B(c_i, 100c^4 \cdot r) \;\subseteq\; N(c_i, 100c^4 \cdot r) \;\subseteq\; B(c_i, 100c^5 \cdot r).\] In our implementation, the Source-Insertion SSSP algorithm from 1 maintains distance estimates \(\delta_s(v)\) such that: \[\operatorname{dist}(v,\{c_1,\ldots,c_i\}) \;\le\; \delta_s(v) \;\le\; (1 + {\varepsilon})\operatorname{dist}(v,\{c_1,\ldots,c_i\})\;\; \text{for all vertices } v\in V.\] Hence, if \(\operatorname{dist}(c_i, v) \leq 100c^4 \cdot r\) then \(\delta_s(v) \leq (1+\varepsilon)100c^4 \cdot r\). Moreover, since \(c \geq 5\) and \({\varepsilon}\in (0, 1)\), it holds that: \[\operatorname{dist}(\{c_1, \ldots, c_i\}, v) \;\leq\; \delta_s(v) \;\leq\; (1+\varepsilon)100c^4 \cdot r \;\leq\; 100c^5 \cdot r,\] where \(\delta_s(v) \;\leq\; (1+\varepsilon)100c^4 \cdot r\) is due to the construction of our forbidding loop. Thus, our implicit approximate ball \(\hat{N} \mathrel{\vcenter{:}}= \{v \in V \mid \delta_s(v) \leq (1+\varepsilon)100c^4 \cdot r\}\) via the Source-Insertion SSSP algorithm satisfies: \[B(c_i, 100c^4 \cdot r) \;\subseteq\; \hat{N} \;\subseteq\; B(\{c_1, \ldots, c_i\}, 100c^4 (1+{\varepsilon}) \cdot r) \;\subseteq\; B(\{c_1, \ldots, c_i\}, 100c^5 \cdot r).\] Therefore, the use of \((1+{\varepsilon})\)-approximate distances does not incur any additional approximation cost.
For efficiency purposes, observe that in our forbidding loop in 5, only the vertex set \(V_t\) is scanned; \(V_t\) consists of the vertices whose distance estimates decreased due to the edge \((s,c_i)\). However, if some vertex \(v \in \hat{N}\) does not belong to \(V_t\) (i.e., \(v \notin V_t\)), then \(\delta_s(v)\) has been decreased earlier due to another center \(c_j\) with \(j \in [1, i-1]\). In turn, the corresponding ball \(B(v, r)\) has already been forbidden, which concludes the correctness of our forbidding loop.
To summarize, since the analysis of [41] already tolerates constant-factor slack in these internal data structures, our modification preserves the constant-factor approximation.
5.1.1.1 Completion of the Proof of [thm:randomizedkzclustering]
Based on our preceding analysis, we can now finish the proof of [thm:randomizedkzclustering], which we restate for convenience.
Proof. The time guarantee follows from 23 8 7 9, and the approximation and correctness guarantees follow from 5.1.1. ◻
6 Deterministic \((k,z)\)-Clustering Algorithm on Graphs↩︎
In this section we give a deterministic instantiation of the template of 4, proving [thm:deterministicclustering]. Recall from the randomized algorithm in 5 that the only randomized component of our \((k,z)\)-clustering algorithm is Cohen’s ball-size estimation [52], used to implement the ball values ; the truncated Dijkstra computations and the SSSP-based forbidding loop are already deterministic. It therefore suffices to estimate ball sizes deterministically. We do so using the bunches and clusters of the Thorup–Zwick distance oracle [4]. First, we give an overview of our proof, then we state Thorup–Zwick distance oracle 6.1 and explain how we use it to provide a deterministic algorithm.
While distance oracles are typically used to answer distance queries between vertex pairs with stretch \(2t-1\), where \(t\) is the number of levels of the oracle (see 6.1), we instead use it to obtain, for every vertex \(v \in V\) and radius \(r > 0\), an approximate neighborhood \(N(v,r)\) as a union of at most \(t+1\) precomputed sets (4 ), whose stored sizes yield a quantity \(\hat{N}(v,r)\) satisfying \[|B(v,r)| \;\le\; \hat{N}(v,r) \;\le\; (t+1) \cdot |B(v, 2\alpha r)| \qquad\text{with } \alpha = 4t-2\] (12 and 13). The deterministic estimation comes at a cost in the running time as well: the oracle preprocessing takes \(\tilde{O}(t \cdot m \cdot n^{1/t})\) time, compared to the near-linear time of the randomized algorithm. The parameter \(t\) thus governs a trade-off between solution quality and running time, and we obtain a deterministic \(O(\mathrm{poly}(t))\)-approximation in \(\tilde{O}\bigl(t \cdot m \cdot n^{1/t} + \tfrac{m}{\varepsilon}\bigr)\) time.
Before describing the construction, we fix the two template parameters for this section. Recall from 4 that the template is governed by two parameters: \(\rho \ge 1\), the slack allowed in the ball values (1 ), and \(c \ge 5\), the radius blow-up allowed in the approximate balls (2 ), subject to \(c \ge \rho^2/2\). The ball values that we construct in 6 satisfy 1 with \(\rho = t+1\), and the underlying approximate neighborhoods satisfy \(B(v,r) \subseteq N(v,r) \subseteq B(v, 2\alpha r)\) with \(\alpha = 4t-2\) (12). Accordingly, we set \[\label{eq:det-params} \rho \mathrel{\vcenter{:}}= t+1 \qquad\text{and}\qquad c \mathrel{\vcenter{:}}= \max\Bigl(8t-4,\;\bigl\lceil\tfrac{(t+1)^2}{2}\bigr\rceil, \;5\Bigr) = \Theta(t^2).\tag{3}\]
6.1 Thorup–Zwick distance oracle↩︎
Given a weighted undirected graph \(G=(V,E,w)\) and an integer \(t \ge 1\), the construction is based on a hierarchy \(V = A_0 \supseteq A_1 \supseteq \cdots \supseteq A_t = \emptyset\). For \(v \in V\) and level \(i \in \{0, \dots, t-1\}\), the pivot \(p_i(v) \mathrel{\vcenter{:}}= \arg\min_{w \in A_i} \operatorname{dist}(v,w)\) is the vertex of \(A_i\) nearest to \(v\). The bunch of \(v\) is \[\mathrm{Bunch}(v) \;\mathrel{\vcenter{:}}=\; \bigcup_{0 \le i \le t-1} \bigl\{w \in A_i \setminus A_{i+1} \;\big|\; \operatorname{dist}(v,w) < \operatorname{dist}(v, A_{i+1})\bigr\},\] and it contains all pivots of \(v\). The cluster of \(w \in A_i \setminus A_{i+1}\) is \(C(w) \mathrel{\vcenter{:}}= \{v \in V \mid \operatorname{dist}(v,w) < \operatorname{dist}(v, A_{i+1})\}\).
Theorem 3 (Thorup–Zwick [4]). There is a deterministic algorithm that, given \(G\) and \(t \ge 1\), computes in \(\tilde{O}(t \cdot m \cdot n^{1/t})\) time the hierarchy, all pivots, and all bunches and clusters together with the associated exact distances, each stored as a list sorted by distance. Moreover, \(|\mathrm{Bunch}(v)| = O(t \cdot n^{1/t})\) for every \(v \in V\), and the total storage is \(O(t \cdot n^{1+1/t})\).
6.1.0.1 Overview: Ball-size estimation via bunches and clusters.
Computing \(|B(v,r)|\) exactly for all \(v \in V\) and \(r \in \mathcal{R}\) is too expensive, since a single ball may contain \(\Omega(n)\) vertices. Instead, we cover each ball by a few of the precomputed sets of 3 and estimate its size from theirs. The covering property we use is the following: for all \(u, v \in V\), either \(u \in \mathrm{Bunch}(v)\), or there exists a level \(i\) such that \(p_i(v) \in \mathrm{Bunch}(u)\) with \(\operatorname{dist}(v, p_i(v)) \le (4t-3) \operatorname{dist}(u,v)\) and \(\operatorname{dist}(u, p_i(v)) \le (4t-3) \operatorname{dist}(u,v)\) (11); in the latter case, \(u \in C(p_i(v))\) by 10. Hence, with \(\alpha := 4t-2\), every ball \(B(v,r)\) is contained in the union of \(\mathrm{Bunch}(v)\) and the clusters \(C(p_0(v)), \dots, C(p_{t}(v))\), each truncated at radius \(\alpha r\), and conversely this union is contained in \(B(v, 2\alpha r)\) (12). Since each of these \(t+1\) sets is stored sorted by distance, the size of each truncation is retrieved in \(\tilde{O}(1)\) time, and their total size \(\hat{N}(v,r)\) satisfies \(|N(v,r)| \le \hat{N}(v,r) \le (t+1)\,|N(v,r)|\), since every counted vertex lies in the union and belongs to at most one truncated cluster per level and at most once to the bunch (13).
Lemma 10 (Bunch–Cluster Duality [4]). For any \(u, w \in V\): \(\; w \in \mathrm{Bunch}(v) \iff v \in C(w)\).
Lemma 11 (Distance Stretch [48]). For any \(u, v \in V\), let \(i^*\) be the smallest index such that \(p_{i^*}(u) \in \mathrm{Bunch}(v)\). Then \[\operatorname{dist}(u,\, p_{i^*}(u)) \;+\; \operatorname{dist}(p_{i^*}(u),\, v) \;\le\; (4t-3)\,\operatorname{dist}(u,v).\]
Given \(G\), apply 3 (Thorup–Zwick– [4]) to build the approximate distance oracle on \(G\). This yields, for each vertex \(v \in V\), an explicitly stored sorted list \(\mathrm{Bunch}(v)\), and for each pivot \(w\), an explicitly stored list \(C(w)\) — both represented as doubly-linked lists, supporting \(O(1)\) deletion. All cluster sizes \(|C(w,\alpha r)|\) and \(|\mathrm{Bunch}(v,\alpha r))|\) are precomputed and stored. The total preprocessing time is \(O(mn^{1/c})\) and the total storage is \(O(mn^{1/c})\) .
6.2 Approximate Balls via Truncated Bunches and Clusters.↩︎
Fix a constant \(\alpha \ge 4t - 2\). For a vertex \(v \in V\) and radius \(r > 0\), define \[N(v,\, r) \;=\; \mathrm{Bunch}(v,\, \alpha r) \;\cup\! \bigcup_{\substack{i \,\in\, [t] \\ d(v,\, p_i(v))\, <\, \alpha r}} C\!\left(p_i(v),\, \alpha r\right). \label{eq:approx95ball95bunch}\tag{4}\]
where \(\mathrm{Bunch}(v, \rho) = \{w \in \mathrm{Bunch}(v) : \operatorname{dist}(v,w) \le \rho\}\) and \(C(w, \rho) = \{u \in C(w) : \operatorname{dist}(u,w) \le \rho\}\) denote the radius-truncated bunch and cluster, respectively.
6.2.0.1 Approximate Ball Size
We never compute the set \(N(v,r)\) explicitly: the sets in 4 may overlap, so evaluating the cardinality of their union would require enumerating their elements, at a cost proportional to their total size, and this for each of the \(O(n \log \Delta)\) pairs \((v,r)\) is too expensive. Instead, we only sum the sizes of the \(t+1\) truncated sets, each of which is available from the sorted lists of 3. The resulting quantity counts each vertex of \(N(v,r)\) once per set containing it, and hence overcounts \(|N(v,r)|\) by at most a factor of \(t+1\) (13):
\[\hat{N}(v, r) = \left|\mathrm{Bunch}(v, \alpha r)\right| + \sum_{\substack{i \in [t] \\ d(v, p_i(v)) < \alpha r}} \left|C\left(p_i(v), \alpha r\right)\right|. \label{eq:det95ball}\tag{5}\]
Our deterministic ball-value estimation is then, for every \(v \in V\) and \(r \in \mathcal{R}\), \[\label{eq:det-value} \mathrm{Value}(B(v,r)) \;\mathrel{\vcenter{:}}=\; r^z \cdot \hat{N}(v,r).\tag{6}\]
By 12 13 together show that 6 satisfies 1 with \(\rho \mathrel{\vcenter{:}}= t+1\):
We will show that \(\hat{N}(v,r)\) is an \(t\) approximate for \(|N(v,r)|\), that is \(|N(v,r)| \le \hat{N}(v,r) \le t |N(v,r)|\) (see 13), also we show that \(\hat{N}(v,r)\) can be computed in \(O(t)\) time in 4, after preprocessing approximate distance oracle.
Lemma 12. For every \(v \in V\) and \(r > 0\), \(B(v,\, r) \;\subseteq\; N(v,\, r) \;\subseteq\; B(v,\, 2\alpha r)\), where \(\alpha \geq 4t - 2\) and \(t\) is the number of levels in the Thorup–Zwick hierarchy.
Proof. We prove the two containments separately.
Part 1: First containment: \(B(v,r) \subseteq N(v,r)\). Let \(u \in B(v,r)\), so \(\operatorname{dist}(u,v) \le r\). We consider two cases:
Case 1: \(u \in \mathrm{Bunch}(v)\). Since \(\operatorname{dist}(u, v) \leq r \leq \alpha r\), we have \(u \in \mathrm{Bunch}(v, \alpha r) \subseteq N(v, r)\).
Case 2: \(u \notin \mathrm{Bunch}(v)\). We will show that \(u\) appears in \(C(p_i(v), \alpha r)\) for some \(i\) with \(d(v, p_i(v)) < \alpha r\). By 11, let \(i^*\) be the largest index such that \(p_{i^*}(v) \in \mathrm{Bunch}(u)\), and set \(w := p_{i^*}(v)\). Then: \[\label{eq:stretch-bound} \operatorname{dist}(v, w) \;\le\; (4t-3)\,\operatorname{dist}(u,v) \;\le\; \alpha\,r.\tag{7}\]
Hence \(d(v,p_{i^*}) < \alpha r\). Now, we will establish \(u \in C(w, \alpha r)\): By 3, \(w = p_{i^*}(v) \in \mathrm{Bunch}(u)\). By 10 (applied with the roles of \(u\) and \(w\) exchanged), \(w \in \mathrm{Bunch}(u) \Rightarrow u \in C(w)\). Since \(\operatorname{dist}(u,w) \le (4t-3)r \le \alpha r\) by Observation 7 , we get \(u \in C(w,\alpha r)\). Hence \(u \in N(v,r)\).
Part 2: Second containment: \(N(v,r) \subseteq B(v, 2\alpha r)\). Let \(u \in N(v,r)\). We consider two cases:
Case 1: \(u \in \mathrm{Bunch}(v, \alpha r)\): By definition of \(\mathrm{Bunch}(v, \alpha r)\) , \(\operatorname{dist}(v,u) \le \alpha r \le 2\alpha r\).
Case 2: \(u \in C(p_i(v), \alpha r)\) for some \(i \in [t]\) with \(d(v, p_i(v)) < \alpha r\): We have \(d(v, p_i(v)) < \alpha r\) (by the condition in the definition of \(N(v,r)\)) and \(d(u, p_i(v)) \le \alpha r\) (since \(u \in C(p_i(v), \alpha r)\)). By the triangle inequality, \(d(u,v) \le d(u, p_i(v)) + d(p_i(v), v) \le \alpha r + \alpha r = 2\alpha r.\) Hence \(u \in B(v, 2\alpha r)\). ◻
Lemma 13. For a fixed \(v\) and \(r\), observe that \(|N(v,r)| \le \hat{N}(v,r) \;\le\; (t+1)\cdot|N(v,\alpha r)|\) .That is, the sum of precomputed cluster sizes is a \((t+1)\)-approximation of \(|N(v,r)|\);
Proof. The first inequality follows from the union bound. For the second inequality, note that each vertex \(u \in N(v,r)\) appears in at most \(t\) of the clusters \(C(p_i(v), \alpha r), i \in [t]\) (one for each level \(i\)) and at most once in the \(\mathrm{Bunch}(v,r)\). ◻
Lemma 14. For all \(v \in V\) and all radii \(r \in \bigl\{\Delta/(2c)^i : i = 0,\ldots,\log_{2c}\Delta + 7\bigr\}\), the values \(\{\hat{N}(v,r)\}\) can be computed in total time \(O(t \cdot n \log \Delta)\).
Proof. There are \(n\) vertices and \(O(\log \Delta)\) candidate radii, giving \(O(n \log \Delta)\) queries in total. We will prove below for each \((v,r)\) takes \(O(t)\) time 4, Hence the total time of taken is \(O(t \cdot n \log \Delta)\).
Observation 4. For any vertex \(v \in V\) and radius \(r \ge 0\), the quantity \(\hat{N}(v,r)\) can be computed in \(O(t)\) time.
Proof. The value \(|\mathrm{Bunch}(v,\alpha r)|\) can be accessed in constant time. The summation involves at most \(t\) terms, and each cluster size \(|C(p_i(v),\alpha r)|\) is precomputed and can be retrieved in \(O(1)\) time. Thus, the total time to evaluate the expression is \(O(t)\). ◻
◻
Appendix↩︎
7 Approximation of \(\mathrm{Value}(\cdot, \cdot)\)↩︎
The static \((k, z)\)-clustering algorithm of Dupre la Tour and Saulpic [41] defines a function \(\mathrm{Value}(B(u, r))\) which satisfies the following inequalities: \[\frac{r^z}{3} \cdot |B(u, r)| \;\leq\; \mathrm{Value}(B(u, r)) \;\leq\; 3 r^z \cdot |B(u, c \cdot r)|,\] for a vertex \(u \in V\), a positive real number \(r\), a constant \(z \geq 1\), and a constant \(c \geq 5\). The arguments presented in Appendix A of [41] can be generalized to work with any constant in the approximation ratio, not just \(3\). Specifically, it suffices that \(\mathrm{Value}(B(u, r))\) satisfy the following inequalities: \[\frac{r^z}{\rho} \cdot |B(u, r)| \;\leq\; \mathrm{Value}(B(u, r)) \;\leq\; \rho r^z \cdot |B(u, c \cdot r)|,\] for any parameter \(\rho \geq 1\) and \(c \geq \frac{\rho^2}{2}\). The approximation ratio of the algorithm is then affected by a factor of \(\rho^2\); hence for constant parameter \(\rho\), the approximation ratio remains a constant factor. The same arguments in Appendix A of [41] can be repeated with \(\rho\) instead of \(3\); for completeness we indicate the lemmas where the necessary adjustments occur:
The first lemma that should be adjusted is Lemma A.1 in [41], where within its proof, the constant \(3\) can be trivially replaced by the parameter \(\rho\). In turn, the constraint on \(c\) becomes \(c \geq \frac{\rho^2}{2}\) instead of \(c \geq 5\).
The second lemma that should be adjusted is Lemma A.5 in [41]. When \(\mathop{\mathrm{cost}}(\text{In}(P_\gamma), C_k)\) is analyzed in the proof of Lemma A.5, the constant \(3\) can be trivially replaced by \(\rho\), since \((r_\gamma)^z \cdot |B(\gamma, r_\gamma)| \;\leq\; \rho \cdot \mathrm{Value}(B(\gamma, r_\gamma))\).
The third lemma that should be adjusted is Lemma A.6 in [41]. When \(\mathop{\mathrm{cost}}(B(x, c \cdot r), \Gamma)\) is analyzed in the proof of Lemma A.6, the constant \(3\) can be trivially replaced by \(\rho\), since \(r^z \cdot |B(x, c \cdot r)| \;\geq\; \frac{\mathrm{Value}(B(x, r))}{\rho}\).
Finally, by combining Lemmas A.5 and A.6 at the end of Appendix A in [41], the extra \(\rho^2\) factor arises in the approximation ratio.
8 \(k\)-Center with Outliers↩︎
We now extend the incremental framework developed in 3 to the \(k\)-center problem with outliers, where up to \(t\) points may be discarded. As before, the key primitive is the incremental SSSP structure of 1. We give two results (i) [lem:outlier-2approx] handles the case of constant \(k\) and achieves an \(2 + \varepsilon\)-approximation, \(\varepsilon > 0\), while having \((1+{\varepsilon})t\) outliers (ii) 22 handles general \(k\) via a randomized bi-criteria guaranty . Both run in \(\tilde{O}(\frac{m}{\varepsilon})\) time.
8.1 2-Approximation for Constant \(k\)↩︎
Proof. We adapt the \(2\)-approximation algorithm of Ding, Yu, and Wang [54] for \(k\)-center with \((1+{\varepsilon})t\) outliers. The algorithm proceeds in \(k\) rounds. In each round it identifies the \(\lceil(1+\varepsilon)t\rceil\) vertices currently farthest from the center set \(C\) — these are the candidate outliers — and selects one of them uniformly at random as the next center. Maintaining the farthest vertices requires knowing \(\mathrm{dist}(v, C)\) for all \(v \in V\) after each center addition, which we handle incrementally: upon adding center \(c_j\) to \(C\), we insert the zero-weight edge \((s, c_j)\) into the SSSP structure of 1. The full procedure is stated as 4. Let \(\hat{d}(\cdot)\) denote the current distance estimates from \(s\). All vertices are stored in a max-heap keyed by \(\hat{d}(v)\).
Lemma 15. Let \(G=(V,E,w)\) be a weighted graph, and let \(C\) be the set of centers returned by 4. Then, with probability at least probability at least \((1-\gamma)(1/(1+\varepsilon)t)^{k-1}\), \(C\) induces an \((2+\varepsilon)\)-approximate solution to the \(k\)-center problem with \(t\) outliers.
Proof. Let \(C^* = \{o_1, \dots, o_k\}\) be an optimal solution, inducing clusters \(O_1, \dots, O_k\), and let \(T^* \subseteq V\) denote the set of \(t\) optimal outliers. Let \(\mathrm{OPT}\) be the optimal radius, i.e., \(\forall i \in [k],\;\forall v \in O_i:\quad \mathrm{dist}(v, o_i) \le \mathrm{OPT}.\)
Let \(C_j = \{c_1, \dots, c_j\}\) be the set of centers chosen after \(j\) iterations. At iteration \(j+1\), let \(Q_{j+1} := \operatorname{Top}_{\lceil (1+\varepsilon)t \rceil} \bigl(\{ \hat{d}(v, C_j) : v \in V \}\bigr)\) be the set of the \(\lceil (1+\varepsilon)t \rceil\) farthest points from \(C_j\), as stored by \(\hat{d}(\cdot)\).
8.1.0.1 Inliers and outliers.
Let \(T^* \subseteq V\) denote the set of \(t\) outliers in the optimal solution. The remaining points \(V \setminus T^*\) are called inliers. Equivalently, the set of inliers is precisely the union of the optimal clusters: \(\bigcup_{i=1}^k O_i = V \setminus T^*\). Let \(\lambda_j\) denote the number of covered clusters after round \(j\).
Lemma 16 (Cluster diameter bound). If \(\{u,v\} \in O_i\), then \(\mathrm{dist}(u, v) \le 2\mathrm{OPT}.\)
Proof. For any \(\{u,v\} \in O_i\), we have \(\mathrm{dist}(v, o_i) \le \mathrm{OPT}\) and \(\mathrm{dist}(u, o_i) \le \mathrm{OPT}\). The claim follows by triangle inequality. ◻
8.1.0.2 Covered clusters.
We say that a cluster \(O_i\) is covered at step \(j\) if \(C_j \cap O_i \neq \emptyset\), and uncovered otherwise.
Lemma 17. At step \(j \ge 1\), either (1) every vertex of \(Q_{j+1}\) is at distance estimate \(\hat{d}(\cdot)\) greater than \((2 + {\varepsilon})\mathrm{OPT}\) from \(C_j\); in this case \(Q_{j+1}\) contains at least \(\lceil(1+\varepsilon)t\rceil-t\;\ge\;\lceil\varepsilon t\rceil\;\ge 1\) inliers, all of which belong to uncovered clusters \((2) \min_{u\in Q_{j+1}}\hat{d}_j(u)\le(2+\varepsilon)\mathrm{OPT}\).
Proof. Suppose \((2)\) is false, i.e.\(\hat{d}_j(u)>(2+\varepsilon)\mathrm{OPT}\) for all \(u\in Q_{j+1}\). If such a \(u\) were an inlier of a covered cluster \(O_i\), then picking \(c\in C_j\cap O_i\) and using Lemma 16 would give \(\hat{d}_j(u) \le (2 + {\varepsilon}) \mathrm{OPT}\), a contradiction. Hence \(Q_{j+1}\) contains no inlier of a covered cluster, so \(Q_{j+1}\subseteq T^*\cup\{\text{inliers of uncovered clusters}\}\), and the number of uncovered-cluster inliers in \(Q_{j+1}\) is at least \(|Q_{j+1}|-|T^*|=\lceil(1+\varepsilon)t\rceil-t\ge\lceil\varepsilon t\rceil\ge 1\) (using \(t\ge1\) and that \(t\) is an integer).
Suppose \((1)\) is false, \((2)\) is trivially true. ◻
Lemma 18. If condition \((2)\) holds of 17, then in this case at most \(\lceil(1+\varepsilon)t\rceil-1\) vertices \(v\in V\) satisfy \(\hat{d}_j(v)>(2+\varepsilon)\mathrm{OPT}\), and — since estimates are non-increasing — the same bound holds at every step \(j'\ge j\).
Proof. Since vertices with estimate exceeding \((2+\varepsilon)\mathrm{OPT}\) lie in \(Q_{j+1}\setminus\{u\}\), and there are at most \(\lceil(1+\varepsilon)t\rceil-1\) of them. Since each \(\hat{d}(v)\) is non-increasing as centers are inserted, the set of vertices exceeding the threshold can only shrink, so the bound persists for all \(j'\ge j\). ◻
Lemma 19 (Progress per iteration). Conditioned on the event that \((1)\) of 17 holds for \(j > 1\), the probability that iteration \(j+1\) selects a vertex from an uncovered cluster is at least \(\frac{\varepsilon}{\lceil (1+\varepsilon) \rceil}.\)
Proof. By \((1)\) of Lemma 17, at least \(\lceil(1+\varepsilon)t\rceil-t\) of the \(\lceil(1+\varepsilon)t\rceil\) vertices of \(Q_{j+1}\) are inliers of uncovered clusters. Since \(c_{j+1}\) is chosen uniformly at random from \(Q_{j+1}\), the claim follows. ◻
Lemma 20. With probability at least \((1-\gamma)(\frac{{\varepsilon}}{\lceil (1+\varepsilon)\rceil})^{k-1}\), the output \(C_k\) of 4 is a \((2+\varepsilon)\)-approximation
Proof. We will prove this by showing that after \(k\) iterations, all clusters \(O_1, \dots, O_k\) are covered with probability at least \((1 - \gamma) \cdot ( \frac{{\varepsilon}}{\lceil (1+\varepsilon) \rceil} )^{k-1}\), Since \(c_1\) is sampled uniformly from \(V\), \(\Pr[c_1 \notin T^*] = 1 -\gamma\); condition on this event, so \(\lambda_1 = 1\). At each iteration \(1<j \le k\), if event \((1)\) of 17 holds, then by 19, the probability of covering a new cluster is at least \(p := \frac{{\varepsilon}}{\lceil (1+\varepsilon) \rceil}\), else by 18, we already have a \((2 + \varepsilon)\) approximate with having \((1+{\varepsilon})t\) outliers. As, we run it for at most \(k-1\) iterations, we get the success probability as \(( \frac{1}{\lceil (1+\varepsilon)t \rceil} )^{k-1}\). Hence for the 4, the success probability is at least \((1 - \gamma) \cdot ( \frac{{\varepsilon}}{\lceil (1+\varepsilon) \rceil} )^{k-1}\). As, every \(O_i\) is covered, by 16, we get \((2+{\varepsilon})\mathrm{OPT}\) approximation. We have the \((1+{\varepsilon})t\) vertices with the largest distance estimate from the centers \(C_k\) as outliers. ◻
Lemma 21. 4 runs in \(\tilde{O}(\frac{m}{\varepsilon})\) total time.
Proof. Exactly \(k\) zero-weight edges are inserted into the SSSP structure, one per center. Since \(k \le m\) , the total number of SSSP updates is at most \(\tilde{O}(\frac{m}{\varepsilon})\), and by 1 guarantees that the total update time is \(\tilde{O}(\frac{m}{\varepsilon})\). By 2, the number of vertices whose distance estimate ever changes is \(\tilde{O}(\frac{m}{\varepsilon})\), so the total cost of all decrease-key operations on the Heap is \(\tilde{O}(\frac{m}{{\varepsilon}})\) time. Identifying \(Q_j\) at each step uses \(\lceil(1+\varepsilon)t\rceil\) extract-max and re-insert operations on heap structure, costing \(O(t\log n)\) per iteration. Hence the overall running time is \(\tilde{O}(\frac{m}{\varepsilon})\). ◻
◻
◻
8.2 Randomized Bicriteria Approximation for General \(k\)↩︎
We give a bicriteria algorithm with following properties.
Lemma 22. There exists a randomized algorithm that computes a \((2 + \varepsilon ,\, O(1/\varepsilon ))\)-bicriteria approximate solution to the \(k\)-center problem with \(t\) outliers on \(G = (V, E, w)\) in \(\tilde{O}(\frac{m}{\varepsilon})\) time, with high probability. Specifically, the returned set \(C\) has covering radius at most \((2+ \varepsilon ) \cdot \mathrm{OPT}\) while having at most \(O(\frac{k \log \frac{1}{\eta}}{\varepsilon} )\) points as centers.
Proof. The proof follows similar to [lem:outlier-2approx], but instead of 19, we have the following 5. Let \(\lambda_j\) count how many optimal clusters intersect the current center set \(C\) at iteration \(j\). Initially, \(\lambda_1 \geq 1\) with probability \(1-\eta\) by random sampling.
Observation 5. In each iteration \(j\), when random sampling from \(Q_j\), with probability at least \(1-\eta\), the algorithm selects a vertex from uncovered cluster, increasing \(\lambda_j\).
Proof. Fix an iteration \(j\) in which at least one optimal cluster is uncovered. We want to show that with probability at least \(1 - \eta\), at least one of the sampled vertices in this iteration belongs to an uncovered cluster.
Step 1: Uncovered cluster inliers dominate \(Q_j\).
Recall that \(Q_j\) consists of the \(\lceil(1+\varepsilon)t\rceil\) vertices with the largest distance estimates \(\hat{d}(\cdot)\) from the current center set. We argue that the points in \(Q_j\) that do not belong to any uncovered cluster number at most \(t\).
Indeed, any inlier of a covered cluster is within \(2 \cdot \mathrm{OPT}\) of some current center (by the triangle inequality through its optimal center), so its distance estimate is small and it does not appear in \(Q_j\). The only remaining candidates for \(Q_j\) that are not from uncovered clusters are the \(t\) outliers. Hence at most \(t\) points in \(Q_j\) are non-uncovered, and at least \(\lceil(1+\varepsilon)t\rceil - t \geq \varepsilon t\) points in \(Q_j\) are inliers of uncovered clusters.
Step 2: Probability that a single sample misses uncovered clusters.
Since at most \(t\) out of \(\lceil(1+\varepsilon)t\rceil\) points in \(Q_j\) are non-uncovered, the probability that a single uniform sample from \(Q_j\) does not land in an uncovered cluster is at most \(\frac{t}{\lceil(1+\varepsilon)t\rceil} \leq \frac{1}{1+\varepsilon}\).
Step 3: Probability that all samples miss.
In iteration \(j\), the algorithm draws \(q := \left\lceil\frac{1+\varepsilon}{\varepsilon} \ln\!\left(\frac{1}{\eta}\right)\right\rceil\) vertices independently and uniformly from \(Q_j\). The probability that all of them miss every uncovered cluster is at most \(\left(\frac{1}{1+\varepsilon}\right)^{q} \leq \left(\frac{1}{1+\varepsilon}\right)^{ \frac{1+\varepsilon}{\varepsilon}\ln(1/\eta)}\). \(\Pr[\text{all sampled vertices miss uncovered clusters}] \leq e^{-\ln(1/\eta)} = \eta\).
Therefore, with probability at least \(1 - \eta\), at least one sampled vertex in iteration \(j\) belongs to an uncovered cluster, which increases \(\lambda_j\) by at least one. ◻
8.2.0.1 Covering all clusters.
Setting \(\eta = \delta/k\) for a desired failure probability \(\delta \in (0,1)\), 5 guarantees that in each iteration \(\lambda_j\) increases by at least one with probability \(1 - \delta/k\). By a union bound over all \(k\) iterations, all optimal clusters are covered simultaneously with probability at least \(1 - k \cdot (\delta/k) = 1 - \delta\). Setting \(\delta = 1/n\) gives a high probability guarantee, with the number of samples per iteration increasing only by a \(\log(kn)\) factor, which is absorbed into the \(\tilde{O}\) notation.
The full procedure is stated as 5. Let \(\hat{d}(\cdot)\) denote the current distance estimates from \(s\).
8.2.0.2 Running time.
Maintaining the max‑heap of distance estimates. All vertices are stored in a max‑heap keyed by their current estimate \(\widehat d(v)\). Whenever the incremental SSSP structure relaxes an edge \((u,v)\) and consequently lowers \(\widehat d(v)\), we perform a decrease‑key operation on \(v\) (cost \(O(\log n)\)). The total number of such heap updates is bounded by \(\tilde{O}(m)\) 2.
Extracting the \(\lceil(1+\varepsilon)t\rceil\) farthest vertices. At the beginning of each of the \(k\) iterations we need the set \(Q_i\) of the \(\lceil(1+\varepsilon)t\rceil\) vertices with the largest current estimate. Using the max‑heap we obtain \(Q_i\) by performing \(\lceil(1+\varepsilon)t\rceil\) extract‑max operations and immediately reinserting the extracted vertices. Each extraction (or reinsertion) costs \(O(\log n)\), hence a single iteration costs \(O(t\log n)\).
Hence the overall running time is \(\tilde{O}(m)\). ◻
9 Cohen’s Algorithm↩︎
Lemma 23 (Cohen’s ball-size estimation, Theorem 5.2 in [52]). There is a randomized algorithm that, given a weighted undirected graph \(G = (V,E,w)\) and a small constant \(\varepsilon > 0\), constructs a data structure with the following properties:
The expected preprocessing time is \(O\!\left(\frac{m \log^{2} n \,+\, n \log^{3} n}{\varepsilon^2}\right)\).
For any query pair \((v,r) \in V \times \mathbb{R}^{+}\), the data structure returns an estimate \(\tilde{b}(v,r)\) of \(|B(v,r)|\), where \(B(v,r)\) denotes the ball of radius \(r\) around \(v\).
The expected query time is \(O(\log \log n)\).
With high probability, for all \((v,r) \in V \times \mathbb{R}^{+}\) it holds that:
\(\dfrac{\left|\,|B(v,r)| - \tilde{b}(v,r)\,\right|}{|B(v,r)|} \;\le\; \varepsilon\).
References↩︎
forster@cs.sbg.ac.at↩︎y.nazari@vu.nl↩︎r.raokamblanagendra@vu.nl↩︎antonis.skarlatos@warwick.ac.uk↩︎Note that in this context “incremental” does not refer to the algorithm being dynamic in the sense that data might be added to the input over time. Later in this paper, we will actually employ an algorithm that is incremental in the dynamic-algorithms sense. To avoid confusion, we will avoid the term “incremental” for the latter.↩︎
This is the only result in the paper where we assume \(k\) is a constant. All other statements hold for any integer \(k\).↩︎
Recall that incremental does not mean the algorithm is dynamic; rather, it means that every prefix of length \(\ell\) of the returned \((k, z)\)-clustering solution induces a constant-factor approximate \((\ell, z)\)-clustering solution.↩︎
The aspect-ratio is the ratio between the largest distance and the smallest non-zero distance.↩︎
The data structure of [47] avoids a usual \(n^{o(1)}\)-factor appearing in partially dynamic \((1+{\varepsilon})\)-SSSP data structures by relying on the fact that edge insertions are only incident to the source.↩︎
Notice that in fact \(B(u, 10c\cdot r)\) is computed, which is even stronger than \(B(u, 10c^2 \cdot r)\) required in the definition of the approximate ball \(N(u, 10c \cdot r)\) (see 4).↩︎
Since 1 requires a directed graph as input, each undirected edge is replaced by two oppositely directed edges with the same weight.↩︎
Note that if \(r = \hat{r}\) then \(\hat{u}_2 = u_2\), and the contradiction already follows since we argued that \(B(u_2, r)\) has been forbidden.↩︎