1 Introduction↩︎

Clustering is a fundamental and well-studied problem in computer science with numerous applications across various domains [1]–[5]. Conceptually, clustering involves partitioning data points into groups such that points within the same group are more similar to each other than to those in different groups, according to some measure of similarity. Clustering algorithms optimize a given objective function, and for \(k\)-clustering problems the goal is to output a set of \(k\) representative points that minimize a \(k\)-clustering objective.

While the graph clustering toolkit for network analysis tasks (e.g., community detection) encompasses a wide range of clustering objectives suited to different scientific communities [6]–[9], researchers have in particular performed experimental studies with \(k\)-clustering objectives on graphs [10], [11]. It has been observed in these experiments that (a) high computational cost and (b) the sensitivity of distances to single edge updates pose a challenge when employing \(k\)-clustering in graphs [11] (see also [9]), which motivates further algorithm design in this direction.

Among the most widely studied \(k\)-clustering objectives are \(k\)-median and \(k\)-means. The \(k\)-median objective is the sum of distances from each point to its closest center, while the \(k\)-means objective is the sum of squared distances from each point to its closest center. A generalization of both is the \((k, z)\)-clustering objective, which is the sum of distances raised to the power \(z\) from each point to its closest center. Hence given a metric space \((\mathcal{X}, \operatorname{dist})\), a set of points \(P \subseteq \mathcal{X}\), and a positive integer \(k \leq |P|\), the goal in the \((k, z)\)-clustering problem is to output a subset \(S \subseteq P\) of at most \(k\) points, referred to as centers, such that the value \(\sum_{p \in P} \operatorname{dist}(p, S)^z\) is minimized. Observe that the \(k\)-median clustering problem corresponds to \(z=1\), and the \(k\)-means clustering problem corresponds to \(z=2\).

The \(k\)-median clustering problem is known to be NP-hard in arbitrary metric spaces [12]. The first approximation algorithms leveraged tree embeddings and polynomial-time algorithms for the tree setting [13], achieving an approximation ratio of \(O(\log n \log\log n)\) [14], [15]; later refined to \(O(\log k \log\log k)\) [16]. The first constant-factor approximation was established in [17] using LP rounding and was later improved to \(3 + \epsilon\) through local search [18]–[20]. Subsequently, approximation ratios below \(3\) were achieved [20]–[22], with the best-known approximation ratio currently standing at \(2+\epsilon\) [23]. Meanwhile, the best known hardness result rules out an approximation factor less than \(1+2/e \approx 1.74\) [24]. Many of the aforementioned algorithmic approaches carry over to \(k\)-means and \((k, z)\)-clustering with worse approximation factors. For the \(k\)-means clustering problem, the best known approximation ratio is \(5+\epsilon\) [25] and the best known hardness result rules out an approximation factor less than \(1+8/e \approx 3.94\) [24], [26].

1.0.0.1 Efficient \(k\)-clustering algorithms.

Fast algorithms have been proposed for the \(k\)-median clustering problem in arbitrary metric spaces with oracle access to the distances between points. Jain and Vazirani [27] developed a deterministic \(6\)-approximation algorithm that runs in \(\tilde{O}(n^2)\) time. Subsequently, Mettu and Plaxton presented another approach for obtaining a constant-factor approximation in \(\tilde{O}(n^2)\) time [28]. Later, they presented a randomized \(O(1)\)-approximation algorithm with a more efficient running time of \(\tilde{O}(nk)\) [29]. As noted by Huang and Vishnoi [30], the algorithm in [29] can be easily generalized to the \((k, z)\)-clustering problem.

1.0.0.2 Graph setting.

In the graph setting, the \((k, z)\)-clustering problem is defined as before, where the metric space is induced by the shortest-path distances in a weighted undirected graph with \(n\) vertices, \(m\) edges, and maximum edge weight \(W\). Here, no oracle access is available, and distance computations must be performed explicitly by the algorithm if needed. As a consequence, although algorithms designed for point sets can be applied in the graph setting, this approach leads to inefficient algorithms. Thorup [31] addressed this issue for the \(k\)-median clustering problem by developing a randomized \((12+o(1))\)-approximation algorithm that runs in \(\tilde{O}(m)\) time.⁴ As noted in [32], it seems plausible that the approach of Thorup [31] generalizes to \((k, z)\)-clustering using recent insights on the primal-dual method used as a subroutine. Very recently, alternative near-linear and almost-linear time constant-factor approximation algorithms based on a greedy approach [32] and local search [33] have been developed. It is worth noting that the fastest constant-factor approximation algorithms for Euclidean \((k, z)\)-clustering can be obtained by running the state-of-the-art graph clustering algorithms on a sparse metric spanner [34]. The graph setting has also received notable attention for the \(k\)-center clustering problem [31], [35]–[38].

1.0.0.3 Dynamic \(k\)-clustering algorithms.

In recent years, the rapid growth and continuous change of data have led to strong interest in developing dynamic \(k\)-clustering algorithms [39]–[46]. The related work most similar to ours is by Cruciani, Forster, Goranci, Nazari, and Skarlatos [43], who study the \(k\)-center clustering problem on dynamic graphs under adversarial edge updates; they achieve for example an amortized update time of \(k n^{o(1)}\) in the incremental setting. Since the shortest-path metric of a graph induces a metric space, it may seem natural to apply algorithms designed for dynamic point sets in metric spaces [39], [40], [42]. However, as noted in [43], this approach leads to inefficient algorithms as discussed in the next paragraph.

1.0.0.4 Comparison of dynamic graphs and dynamic point sets.

Let us briefly highlight the key differences and challenges between the model with dynamic graphs, which we also consider in this paper, and the model with dynamic point sets in metric spaces [39], [40], [42]. In the model with dynamic point sets, the adversarial updates are point insertions or point deletions. On the other hand, in our model with dynamic graphs, the adversarial updates are edge insertions or edge deletions. This distinction introduces two main challenges, as explained in [43]: (i) there is no oracle access to all-pairs shortest-path distances, and (ii) a single edge update can affect multiple distances simultaneously, whereas a point update does not affect distances between previously inserted points. As a result, directly applying black-box algorithms designed for dynamic point sets to dynamic graphs is very inefficient.

To the best of our knowledge, no algorithms have been developed so far for the \(k\)-median, \(k\)-means, or their generalization \((k, z)\)-clustering on graphs undergoing edge updates. For this reason, a natural question arises about the efficiency of dynamic algorithms for the \((k, z)\)-clustering problem on dynamic graphs:

1.1 Our Contributions↩︎

In this paper, we answer this question in the affirmative for the incremental setting, in which the weighted undirected graph undergoes adversarial edge insertions. We believe that the incremental setting is particularly interesting and well-motivated from a practical point of view, as there exist inherently incremental graphs in practice. For example, real-world graphs such as co-authorship networks are incremental, since the fact that two scientists have co-authored a research paper (almost) never changes over time.

Throughout the paper, we assume an oblivious adversary for our randomized results. An oblivious adversary fixes the entire sequence of updates before the algorithm begins. Namely, the adversary cannot adapt the edge updates based on the (randomized) outputs of the algorithm during the execution. Our central result is a highly efficient incremental algorithm—independent of the parameter \(k\)—that maintains a constant-factor bicriteria approximate solution of size \(\tilde{O}(k)\) (see 3), which is optimal up to polylogarithmic factors for the \((k,z)\)-clustering problem.

For clarity of presentation, in [thm:incr95alg] we hide the dependence on \(z\) in the approximation ratio—which is \(O((1+\epsilon)^{2z})\)—and the dependence on \(\epsilon\) and \(W\) in the update time. By combining [thm:incr95alg] with our incremental reduction algorithm (in [thm:bicr95to95kzclustering]), we obtain our main result.

For clarity of presentation, in [thm:mainthm95kzcluster] (our incremental algorithm) we hide the dependence on \(W\) inside the notation \(\tilde{O}(\cdot)\), which we use to suppress polylogarithmic factors in \(nW\). The hidden dependence on \(\lambda\) in the \(O(1)\)-approximation ratio is \(O(\lambda^{6z})\).

1.1.0.1 Comparison between \((k, z)\)-clustering and \(k\)-center.

Let us make a few remarks about our results in comparison with the results in [43], which studies the \(k\)-center objective. In the work by Cruciani, Forster, Goranci, Nazari, and Skarlatos [43], the most challenging setting was the incremental one; the decremental setting naturally follows from the connection between the maximal independent set problem and the \(k\)-center clustering problem. Moreover, the fully dynamic setting follows from a reduction to fully dynamic approximate SSSP that “simulates” a run of a static algorithm after each adversarial edge update. The latter approach would also work for fully dynamic \((k, z)\)-clustering, but because of the larger constants in the approximation ratio would not be competitive with the naive approach of recomputing from scratch on a dynamic spanner after each adversarial edge update.

In the incremental setting, the approach of [43] is also to first maintain a bicriteria approximate solution and then construct a \(k\)-center solution on top of it. Our update time guarantee in [thm:incr95alg] matches theirs (for bicriteria approximation), and the total update times match the static runtime up to subpolynomial factors. Their second step, which converts the bicriteria approximate solution into a \(k\)-center solution, exploits a fast dynamic maximal independent set algorithm [47], [48] as a black box. In contrast, for the \((k, z)\)-clustering problem we need to take additional steps using a dynamic spanner algorithm.

1.2 Structure of the Paper↩︎

We provide a technical overview in 2, followed by basic preliminaries in 3. In 4, we present a static version of the bicriteria approximation which helps introduce the ideas behind the incremental version in Section 5. In particular, it shows that the order of the radii can be made non-decreasing without affecting the approximation ratio by more than a constant factor. In 6, we combine our incremental bicriteria approximation algorithm with our incremental reduction algorithm to address the \((k, z)\)-clustering problem on incremental graphs.

2 Technical Overview↩︎

In the following, we give a brief overview of our main technical contributions for the incremental setting, where the input graph \(G = (V, E, w)\) undergoes edge insertions sent by the adversary. The goal is to develop an efficient incremental constant-factor approximation algorithm for the \((k, z)\)-clustering problem on graphs. Our incremental \((k, z)\)-clustering algorithm consists of two subroutines. The first subroutine described in 5, is an incremental \((O(1), O(\log^3 n \, \log_{1+\epsilon}nW))\)-bicriteria approximation algorithm for the \((k, z)\)-clustering problem on graphs. The second subroutine described in 6, efficiently converts the previous bicriteria approximate solution into a constant-factor approximate \((k, z)\)-clustering solution after every adversarial edge insertion.

2.1 Basis of Our Incremental Bicriteria Approximation Algorithm↩︎

The basis of our incremental \((O(1), O(\log^3 n \log_{1+\epsilon} nW))\)-bicriteria approximation algorithm for the \((k, z)\)-clustering problem is the static \((O(1), O(\log^2 n))\)-bicriteria approximation algorithm by Mettu and Plaxton [29], henceforth referred to as the MP-bi algorithm. A high-level overview of the static MP-bi algorithm is presented in the next paragraph.

2.1.0.1 MP-bi algorithm.

Let \(U_0 = V\) be the whole vertex set. The MP-bi algorithm performs at most \(t \mathrel{\vcenter{:}}= O(\log \frac{n}{k})\) iterations, where at the \(i\)-th iteration:

1. A candidate set \(S_i\) is constructed by sampling a small subset of \(U_i\), where \(|S_i| = \tilde{O}(k)\).

2. The smallest radius \(\nu_i\) is computed such that the ball \(B_i\) of radius \(\nu_i\) around \(S_i\) contains a constant fraction \(\beta\) of vertices from \(U_i\) (i.e., \(|B_i \cap U_i| \geq \beta |U_i|\)).

3. The ball \(B_i\) is removed from \(U_i\), and the MP-bi algorithm recurses on the remaining vertices \(U_{i+1} \coloneq U_i \setminus B_i\).

In the incremental setting, the adversary inserts new edges into the graph; our aim is to design an incremental version of the MP-bi algorithm under adversarial edge insertions. We refer to the \(i\)-th iteration of the MP-bi algorithm as the \(i\)-th level. Thus, our goal is to incrementally maintain the data structures of the MP-bi algorithm at each level \(i\).

2.1.1 Challenges in the Incremental Setting↩︎

The central step of the MP-bi algorithm is its second step, where the smallest radius \(\nu_i\) is computed. Under edge insertions the distances are non-increasing, and so for a fixed radius \(\nu_i\), the ball \(B_i\) can only “receive” new vertices. In this case, whenever a ball \(B_i\) contains more than a \(\beta\) fraction of vertices from \(U_i\), the radius \(\nu_i\) should be decreased accordingly. The core issue however, is that the subsequent set \(U_{i+1}\) of remaining vertices can change in a fully dynamic manner, as follows:

• Vertices and edges can be removed from the set \(U_{i+1}\) by entering the ball at a previous level. This occurs when a newly inserted adversarial edge decreases the distance between the candidate set \(S_j\) and a vertex in \(U_{i+1}\) to at most \(\nu_j\), for some previous level \(j < i + 1\).

• Vertices and edges can be added to the set \(U_{i+1}\) by leaving the ball at a previous level. This occurs when the radius \(\nu_j\) is decreased accordingly because many vertices enter the ball \(B_j\) due to a newly inserted adversarial edge, for some previous level \(j < i+1\).

As a consequence, the current candidate set \(S_{i+1}\) which was sampled from the old set \(U_{i+1}^\text{(old)}\), may no longer be a good representative in the new set \(U_{i+1}\). For this reason, a new candidate set \(S_{i+1}\) should be sampled from the modified set \(U_{i+1}\), and the new radius \(\nu_{i+1}\) should be computed. In other words, the first two steps of the MP-bi algorithm should be repeated at level \(i+1\). The second step of the MP-bi algorithm in the incremental setting can be implemented straightforwardly by maintaining the ball \(B_j\) and the radius \(\nu_j\) at each level \(j\), as follows:

• either by using a fully dynamic SSSP (single-source shortest paths) algorithm with a super-source attached to the candidate set \(S_j\),

• or by restarting an incremental SSSP algorithm with a super-source attached to the candidate set \(S_j\), whenever the set \(U_j\) is modified.

The first option of employing a fully dynamic SSSP algorithm has a prohibitive update time. The second option of employing an incremental SSSP algorithm depends on the total number of times any set \(U_j\) is modified, which is naively proportional to the number of distinct sequences of the radii \(\nu_j\). Therefore, we can infer that the total update time of the second option depends on the number of distinct sequences of the radii \(\nu_j\).

2.1.1.1 Number of distinct sequences of the radii.

Even when the radii are powers of \((1+\epsilon)\) and the number of levels \(t\) is \(O(\log n)\), the number of distinct sequences of the radii \(\nu_j\) is naively at least: \[\Omega\left( \min\left( \left(\log_{1+\epsilon} nW\right)^{\log n},\, m \right) \right),\] where \(W\) is the maximum weight of an edge, and thus \(nW\) is the maximum possible distance between two vertices in the graph. The first term is because the new radius \(\nu_j\) may differ arbitrarily from the old radius \(\nu^\text{(old)}_j\) at level \(j\), after repeating the second step of the MP-bi algorithm. The second term is because the sequence of the radii could change after each adversarial edge insertion.

For the second straightforward option, an incremental SSSP algorithm is restarted at most \(t = O(\log n)\) times (for the \(t\) sets \(U_j\)) per distinct sequence of the radii. As a result, the total update time required for the second straightforward option is at least: \[\Omega\left( \min\left( \left(\log_{1+\epsilon} nW\right)^{\log n},\, m \right) \right) \cdot \log n \cdot \text{ the running time of an SSSP algorithm.}\] In other words, the total update time required for the second straightforward option is at least \(\Omega(m \cdot (\log_{1+\epsilon} nW)^{\log n})\), which is excessively high.

2.2 Incremental Bicriteria Approximation Algorithm↩︎

In principle our approach follows the second option, which is to restart an incremental SSSP algorithm as many times as the number of distinct sequences of the radii \(\nu_i\). However, to overcome the issue of exponentially many distinct sequences of \(\nu_i\) while ensuring constant-factor approximation, we introduce a refined and elegant solution for managing the radii \(\nu_i\). Our solution is a variant of the MP-bi algorithm and relies on two properties that are enforced on the radii.

The first property which is referred to as the non-increasing property, is that the value of each radius is non-increasing over time (i.e., the value of a specific \(\nu_i\) either decreases or remains the same). By the non-increasing property, along with the facts that each radius is a power of \((1+\epsilon)\) and that \(t = O(\log n)\), we argue that there are at most \(O\left(\log_{1+\epsilon} nW \cdot \log n\right)\) distinct sequences of radii. In turn, the update time becomes: \[O\left(\log_{1+\epsilon} nW \cdot \log n\right) \cdot \log n \cdot \text{ the update time of an incremental SSSP algorithm.}\]

Nonetheless, since the non-increasing property is enforced, there is no guarantee on the approximation ratio. In particular, simultaneously enforcing the non-increasing property and maintaining \(t = O(\log n)\) levels may lead to decisions that do not guarantee a constant-factor approximation. To that end, in order to maintain a constant-factor approximation, we establish the following crucial structural property of the MP-bi algorithm:

We refer to this second property as the monotonicity property of the radii. Using the monotonicity property, along with the fact that the distances are non-increasing in the incremental setting (under adversarial edge insertions), we show that the approximation ratio is constant. As a warm-up, we introduce the monotonicity property also in the static setting. Our static MP-bi variant enforces the monotonicity property from level \(0\) up to level \(t\), as follows:

1. If \(\nu_i \geq \nu_{i-1}\), then our MP-bi variant retains the radius \(\nu_i\).

2. If \(\nu_i < \nu_{i-1}\), then our MP-bi variant replaces the value of the radius \(\nu_i\) with the (updated) value of the radius \(\nu_{i-1}\) from the previous level.

Notably, we prove that this modification preserves the constant-factor approximation of the MP-bi algorithm. Therefore, the core idea of our approach is to enforce the non-increasing property to achieve efficient update time, while relying on the monotonicity property to guarantee a constant-factor approximation.

2.2.1 Combining Non-Increasing and Monotonicity Properties in the Incremental Setting↩︎

In the incremental setting, we demonstrate how both the non-increasing and monotonicity properties can be enforced simultaneously, and how the monotonicity property can be leveraged to argue about the approximation ratio. Let \(\nu_i^\text{(old)}\) be the old radius at level \(i\), and \(\nu_i\) be the new radius at level \(i\) maintained by the incremental algorithm after an adversarial edge insertion.

Consider the set \(U_i\) at level \(i\), and note that after an adversarial edge insertion some vertices may move closer to the corresponding candidate set \(S_i\). In other words, the ball \(B_i\) may receive new vertices, causing \(|B_i \cap U_i|\) to exceed \(\beta |U_i|\) and the radius \(\nu_i\) to be decreased accordingly (i.e., \(\nu_i < \nu_i^\text{(old)}\)). Consider a vertex \(v \in U_i\) that is within a distance of \(\nu^\text{(old)}_i\) from the candidate set \(S_i\). Since under edge insertions the distances are non-increasing, the distance between \(v\) and \(S_i\) remains at most \(\nu_i^\text{(old)}\). However, it is possible that the distance between \(v\) and \(S_i\) is greater than the new radius \(\nu_i\), which implies that the vertex \(v\) does not belong to the ball \(B_i\) anymore. In this case, we add such a vertex \(v\) in a set \(Z\), which we call the leaking set. Specifically, the leaking set \(Z\) contains all vertices that have exited a ball from a previous level and have leaked to a subsequent level.

Since the set \(U_{i+1}\) may be modified, we repeat the first two steps of the MP-bi algorithm at level \(i + 1\): we resample a fresh candidate set \(\tilde{S}_{i+1}\), add it to the old candidate set \(S_{i+1}\), and compute a suggested radius \(\tilde{\nu}_{i+1}\) based on the second step of the MP-bi algorithm. The difference between our incremental algorithm and the straightforward option lies in the fact that the new radius \(\nu_{i+1}\) is updated according to our MP-bi variant, while enforcing both the non-increasing and monotonicity properties:

1. If \(\tilde{\nu}_{i+1} \geq \nu_{i+1}^\text{(old)}\), then our incremental algorithm ignores the suggested radius \(\tilde{\nu}_{i+1}\) and retains the old radius \(\nu_{i+1}^\text{(old)}\) (i.e., \(\nu_{i+1} = \nu_{i+1}^\text{(old)})\).

2. Else if \(\tilde{\nu}_{i+1} < \nu_i\), then our incremental algorithm sets the new radius \(\nu_{i+1}\) to the current radius \(\nu_i\) of the previous level.

3. Otherwise, our incremental algorithm sets the new radius \(\nu_{i+1}\) to the suggested radius \(\tilde{\nu}_{i+1}\).

The first condition enforces the non-increasing property, while the first and second conditions enforce the monotonicity property. As a consequence of the non-increasing property, the number of distinct sequences of the radii \(\nu_j\) is reduced to \(O(\log n \cdot \log_{1+\epsilon} nW)\). Although we prove that the monotonicity property preserves the constant-factor approximation of the MP-bi algorithm in both the static and incremental settings, in the incremental setting we must also handle the leaking set, which poses an additional challenge. Recall that the leaking set contains vertices that have exited a ball at a previous level and have leaked into a subsequent level.

2.2.1.1 Role of the leaking set.

Since the non-increasing property is enforced for efficiency reasons, in order to identify a \(\beta\) fraction of vertices from \(U_{i+1}\) (as dictated by the second step of the MP-bi algorithm), we may need to use some vertices from the leaking set \(Z\). In the analysis, we prove that a suitable subset of the leaking set \(Z\) exists. Finding a ball \(B_{i+1}\) containing a constant fraction \(\beta\) of vertices from \(U_{i+1}\) (second step of the MP-bi algorithm), and removing \(B_{i+1}\) from \(U_{i+1}\) (third step of the MP-bi algorithm) is important for maintaining at most \(t = O(\log n)\) levels.

To appropriately provide an upper bound on the assigned cost of leaked vertices, we leverage the monotonicity property, as described in the next paragraph. The monotonicity property acts as a glue, ensuring both the non-increasing property (i.e., efficiency) and the constant-factor approximation are maintained.

2.2.1.2 Assigned cost of the leaking set.

Roughly speaking, subsets of the leaking set \(Z\) are distributed among the sets \(U_i\) for which the corresponding suggested radius \(\tilde{\nu}_i\) is greater than the current radius \(\nu_i^\text{(old)}= \nu_i\). For a fixed vertex \(v \in U_i\) that belongs to the leaking set \(Z\), there is a crucial structural observation to be made: The vertex \(v\) must have entered the set \(U_i\) from a previous level \(j \leq i\). Thus, the vertex \(v\) is within a distance of at most \(\nu_j^\text{(old)}\) from the candidate set \(S_j\). Observe also that the vertex \(v\) may be far from the candidate set \(S_i\). Since under edge insertions the distance between \(v\) and \(S_j\) remains at most \(\nu_j^\text{(old)}\) and \(\nu_j^\text{(old)}\leq \nu^\text{(old)}_i = \nu_i\) by the monotonicity property, we can charge for the vertex \(v\) a cost of \(\nu_i\).

Therefore using the monotonicity property, we can argue that each relevant vertex of any set \(U_i\) can be charged a cost of \(\nu_i\). This in turn helps us to upper bound the approximation ratio of our incremental algorithm, while ensuring that the value of the last level \(t\) remains \(O(\log n)\) throughout the algorithm.

2.3 Maintaining \((k, z)\)-Clustering on Bicriteria Approximate Solution↩︎

So far, we have described how our incremental algorithm maintains a constant-factor bicriteria approximate solution \(S \subseteq V\) of size \(\tilde{O}(k)\). The bicriteria approximate solution \(S\) induces a dynamic \((1 + \epsilon)\)-metric space \((P, \operatorname{d})\)⁵ by maintaining incremental \((1+\epsilon)\)-approximate SSSP algorithms for each vertex in \(S\) (i.e., for each node in \(P = S\)). We “dynamize” a known argument to show that the optimal \((k, z)\)-clustering solution on the \((1 + \epsilon)\)-metric space \((P, \operatorname{d})\), with appropriate weights on the nodes in \(P\), is an \(O(1)\)-approximation to the optimal \((k, z)\)-clustering solution on the graph \(G\) (see 27).

Over the course of the adversarial edge insertions to the incremental graph \(G\), both the set \(P\) and the weights of nodes in \(P\) change at most \(\tilde{O}(1)\) times. The set \(P\) can change because the bicriteria approximate solution \(S\) may receive at most \(\tilde{O}(k)\) new vertices due to an adversarial edge insertion into \(G\). We emphasize that, for the efficiency of all the subroutines of our incremental \((k, z)\)-clustering algorithm, it is important that the total number of vertices that ever belong to \(S\) (and in turn in \(P\)) is at most \(\tilde{O}(k)\). Additionally, the distance between any pair of nodes in \(P\) may decrease at most \(\tilde{O}(1)\) times, resulting in a total of \(\tilde{O}(k^2)\) distance decreases.

The straightforward approach for maintaining an approximate \((k, z)\)-clustering on \((P, \operatorname{d})\) would be to recompute it from scratch in time \(\tilde{O}(|P| k) = \tilde{O}(k^2)\) after every change to the set \(P\) or to the distance function \(\operatorname{d}\). This straightforward approach would result in a total update time of \(\tilde{O} (k m^{1+o(1)} + k^4)\) for our overall incremental \((k, z)\)-clustering algorithm, which implies an amortized update time of \(k n^{o(1)}\) for any \(k \leq m^{1/3 + o(1)}\). To obtain an update time close to \(k\) for the full parameter range, we instead employ an approach involving a dynamic spanner algorithm. At a high level, since we achieve vertex sparsification via the bicriteria approximate solution \(S\), we exploit it further by performing edge sparsification on top of the vertex-sparsified graph \(H = (P, P \times P)\) whose edges are weighted by approximate distances in \(G\).

2.3.0.1 Our approach.

In more detail, we view \((P, \operatorname{d})\) as a complete graph \(H\) with \(\tilde{O}(k^2)\) edges, where the weight of an edge \((x, y)\) in \(H\) corresponds to the approximate distance between \(x\) and \(y\) in \(G\). We further bin the edges of \(H\) into weight classes and maintain a fully dynamic \(O(\lambda)\)-spanner of size \(\tilde{O} (k^{1+1/\lambda})\) on the edges of each weight class [49]. The union \(\tilde{H}\) of these spanners is a \(O (\lambda)\)-spanner for \(H\) of size \(\tilde{O} (k^{1+1/\lambda})\); that is, \(\tilde{H}\) is a subgraph of \(H\) (in terms of edges) in which the distance between every pair of vertices in \(H\) is preserved up to a multiplicative factor of \(O(\lambda)\). This dynamic spanner algorithm [49] can deal with adversarial edge updates in polylogarithmic time per update.

Since the changes to the vertex set of \(H\) (and of \(\tilde{H}\)) occur only in \(\tilde{O}(1)\) many batches, we can restrict the dynamic spanner algorithm to adversarial edge insertions by simply restarting it after every batch of vertex insertions. Since distances in \(G\) are non-increasing, each edge appears at most once in each weight class in between restarts and thus the total update time for maintaining the spanner \(\tilde{H}\) is \(\tilde{O} (k^2)\). As the final step of handling each of the \(m\) adversarial edge insertions to \(G\), we compute a \((k, z)\)-clustering solution on \(\tilde{H}\) in time \(\tilde{O} (k^{1+1/\lambda})\) from scratch using one of the state-of-the-art static \((k, z)\)-clustering algorithms [31]–[33]. Overall, all these steps result in an incremental constant-factor approximation \((k, z)\)-clustering algorithm with a total update time of \(\tilde{O}(k m^{1+o(1)}+ k^{1+\frac{1}{\lambda}} m)\) and an amortized update time of \(\tilde{O}(k n^{o(1)}+ k^{1+\frac{1}{\lambda}})\), where \(\lambda \geq 1\) is an arbitrary fixed constant.

3 Preliminaries↩︎

Consider a weighted undirected graph \(G = (V, E, w)\) with nonnegative weights. We denote by \(n \mathrel{\vcenter{:}}= |V|\) the number of vertices, by \(m \mathrel{\vcenter{:}}= |E|\) the number of edges, and by \(W\) the maximum weight of an edge.⁶ For a vertex \(v \in V\) and a subset of vertices \(S \subseteq V\), let \(\operatorname{dist}(v, S) \mathrel{\vcenter{:}}= \min_{s \in S} \operatorname{dist}(v, s)\) be the distance between the vertex \(v\) and the set \(S\). We write \(\operatorname{dist}_H(\cdot, \cdot)\) to explicitly denote the corresponding distance in a graph \(H\); when the subscript is omitted, it refers to \(\operatorname{dist}_G(\cdot, \cdot)\).

The \((k,z)\)-clustering problem includes the problems of \(k\)-median (\(z=1\)) and \(k\)-means (\(z=2\)). A \((k, z)\)-clustering instance is the triple consisting of the given input object, the integer parameter \(k\), and the constant \(z\). Any subset of vertices \(S \subseteq V\) with size at most \(k\) is referred to as a (feasible) solution, and its cost is referred to as its \((k,z)\)-clustering cost. Hence, the goal of the \((k,z)\)-clustering problem can be rephrased as finding a solution \(S\) with minimum \((k,z)\)-clustering cost \(\text{OPT}\mathrel{\vcenter{:}}= \min_{S \subseteq V: |S| \leq k} \text{cost}^z(S)\). The value \(\text{OPT}\) is called optimal \((k,z)\)-clustering cost, and a solution that minimizes the cost is called an optimal \((k,z)\)-clustering solution.

Our incremental reduction algorithm in 6 deals with weighted \((k, z)\)-clustering instances on a subgraph \(H\), where \(H\) contains both edge and vertex weights.

Our incremental algorithms utilize the following incremental \((1+\epsilon)\)-approximate single-source shortest paths (SSSP) algorithm. We note that similar results have been known implicitly for undirected graphs; these were randomized and assumed an oblivious adversary [50]–[52].

For a fixed a subset of vertices \(S \subseteq V\) and a positive real number \(r\), the set \(\operatorname{Ball}(S, r) \mathrel{\vcenter{:}}= \{v \in V \mid \operatorname{dist}(v, S) < r\}\) denotes the open ball of radius \(r\) around \(S\), and the set \(\operatorname{Ball}[S, r] \mathrel{\vcenter{:}}= \{v \in V \mid \operatorname{dist}(v, S) \leq r\}\) denotes the closed ball of radius \(r\) around \(S\). Throughout our algorithms, we use incremental \((1+\epsilon)\)-approximate SSSP algorithms \(\mathcal{A}\) (1) with a super-source being a fixed set \(S\), providing distance estimates \(\delta_S(\cdot)\). Hence, we extend the definition of balls as follows:

• \(\operatorname{Ball}(S, r, \delta_S) \mathrel{\vcenter{:}}= \{v \in V \mid \delta_S(v) < r\}\) to denote the open ball of radius \(r\) around \(S\) using the distance estimates \(\delta_S(\cdot)\).

• \(\operatorname{Ball}[S, r, \delta_S] \mathrel{\vcenter{:}}= \{v \in V \mid \delta_S(v) \leq r\}\) to denote the closed ball of radius \(r\) around \(S\) using the distance estimates \(\delta_S(\cdot)\).

A dynamic algorithm has amortized update time \(u(n, m)\) if its total time spent for processing any sequence of \(\ell\) adversarial updates is bounded by \(\ell \cdot u(n, m)\). Throughout this paper, whenever we write that an event holds with high probability, we mean that it holds with probability at least \(1 - O(1/n^c)\) for some positive constant \(c\). We also make use of the following concentration bounds in our proofs.

4 Static Bicriteria Approximation \((k,z)\)-Clustering Algorithm↩︎

We denote by MP-bi the \((O(1), O(\log^2 n))\)-bicriteria approximation algorithm of Mettu and Plaxton [29]. In this section, we present a variant of the MP-bi algorithm that runs in time \(O(m \log^2 n)\); the pseudocode of our variant is provided in Algorithm 1.

4.0.0.1 State of our MP-bi variant.

Our variant utilizes the same data structures as the MP-bi algorithm. Specifically, Algorithm 1 consists of multiple levels starting from \(0\). The last level of the algorithm is denoted by \(t\), and by construction the value of \(t\) is upper bounded by \(O(\log n)\). At each level \(i \in [0, t]\), the algorithm constructs an execution set \(U_i\), a candidate set \(S_i\), defines a radius \(\nu_i\), and constructs a ball \(B_i\). The bicriteria approximate solution \(S\) is then the union of all candidate sets, that is, \(S \mathrel{\vcenter{:}}= \bigcup_{i=0}^t S_i\). The algorithm also constructs an assignment \(\sigma: V \to S\), that maps each vertex to a candidate center in \(S\) at a determined distance. The parameters used in the algorithm satisfy the following conditions: \(\alpha \ge 1\) is a sufficiently large constant, and \(\beta, \epsilon \in (0,1)\) are small constants.

4.0.0.2 High-level overview of our MP-bi variant.

Roughly speaking, our variant of the MP-bi algorithm proceeds in iterations. In the \(i\)-th iteration, it samples a set of candidate centers \(S_i\) and computes the smallest radius \(\tilde{\nu}_i\), which is a power of \((1+\epsilon)\), such that the ball of radius \(\tilde{\nu}_i\) around \(S_i\) covers a constant fraction \(\beta\) of the execution set \(U_i\). The actual radius is then set to \(\nu_i \mathrel{\vcenter{:}}= \max(\tilde{\nu}_i, \nu_{i-1})\) in order to enforce the monotonicity property on the radii. This is a key property mainly needed for the incremental setting, which we discuss in detail in 5 (see [property95rad953] in 5). The \(i\)-th ball \(B_i\) is the subset of the ball of radius \(\nu_i\) around \(S_i\) that is contained within \(U_i\) (see Line [line:construct95Bi] in 1). The vertices in \(B_i\) are assigned to candidate centers in \(S_i\) via the assignment \(\sigma\). The \((i+1)\)-th execution set \(U_{i+1}\) is then defined as \(U_i\) without \(B_i\), and the next iteration proceeds.

The intuition is that the algorithm hits large clusters with high probability by sampling a subset of size \(|S_i| = \Theta(k \log n)\) per level. Subsequent iterations are then responsible for hitting the smaller clusters. Since the size of \(U_i\) decreases by at least a constant factor \((1-\beta)\), there are at most \(O(\log n)\) iterations (levels). Thus with high probability, the size of the bicriteria approximate solution \(S = \bigcup_{i=0}^t S_i\) is upper bounded by \(\tilde{O}(k)\).

4.0.0.3 Implementation of Line [line:dijkstra].

The radius \(\tilde{\nu}_i\) is computed using a single-source shortest paths algorithm by connecting each vertex \(v \in S_i\) to a super-source via zero-weight edges. Hence, the step in Line [line:dijkstra] of 1 takes \(O(m \log n)\) time. Observe that the exploration of \(\operatorname{Ball}[S_i, \nu_i]\) is not restricted to \(U_i\), because it may traverse edges outside \(U_i\) to reach some vertices within \(U_i\).

4.0.0.4 Differences between 1 and MP-bi algorithm.

The main difference between our MP-bi variant and the standard MP-bi algorithm lies in Line [line:max95nu], where Algorithm 1 enforces a non-decreasing order of the radii. We leverage this monotonicity property on the radii later in the dynamic setting. We also note that Algorithm 1 has been adjusted in order to work with graphs and discrete distances of powers of \((1+\epsilon)\), while the original MP-bi algorithm works with point sets and non-discrete distances. The discrete distances on the radii that are powers of \((1+\epsilon)\) are needed to achieve efficiency in the dynamic setting. Since our static 1 differs from the original MP-bi algorithm, we present its analysis in 4.1.

4.1 Analysis of the MP-bi Variant↩︎

Mettu and Plaxton prove in [29] that the MP-bi algorithm produces with high probability a constant-factor approximate solution of size at most \(O(k \log^2 n)\). Our aim is to show that our MP-bi variant provides the same guarantees, as demonstrated in Theorem [thm:variant95approx].

Our goal in this section is to prove [thm:variant95approx], and its analysis is divided into four subsections, as outlined below. First, in 4.1.1 we provide an upper bound on \(|S|\). Next, in 4.1.2 we provide an upper bound on \(\operatorname{cost}^z(S)\). Then, in 4.1.3 we provide a lower bound on the optimal cost in terms of \(\operatorname{cost}^z(S)\). Finally, in 4.1.4 we conclude the proof of [thm:variant95approx]. We remark that the essential ideas in the analysis are similar to those in [29].

4.1.1 Size of the Bicriteria Approximate Solution↩︎

4.1.2 Upper Bound on the Cost of the Bicriteria Approximate Solution↩︎

4.1.3 Lower Bound on the Optimal Solution↩︎

We continue with the lower bound on the optimal \((k, z)\)-clustering cost, adapting the analysis in [29]. We fix a positive real number \(\gamma\) such that \(\beta < \gamma < 1\), and we define \(\nu^*_i\) and \(\mu^*_i\) for a fixed level \(i \in [0, t]\), as described in Definition 5 and Definition 6 respectively.

Observe that for a fixed level \(i: 0 \leq i < t\), we can think of \(\tilde{\nu}_{i}\) computed in Line [line:dijkstra] of 1 as being obtained by rounding \(\nu_{i}^*\) to the next power of \((1+\epsilon)\).

We point out that in the above definition, the vertices of \(U_i\) that are exactly at distance \(\mu_{i}^*\) from \(X_i\) belong to both \(\operatorname{Ball}[X_i, \mu_i^*]\cap U_i\) and \(U_i\setminus \operatorname{Ball}(X_i, \mu_i^*)\). The main probabilistic claim in [29] is Lemma 3.3, restated below as [lem:nu602mu]. We observe that in our context, analogous guarantees apply with a similar proof provided in 7 for completeness.

Even though 2 provides an upper bound for \(\tilde{\nu}_{i}\), recall that Algorithm 1 uses the radius \(\nu_i\) computed in Line [line:max95nu], which is at least \(\tilde{\nu}_{i}\). In particular, we upper bound the cost of the bicriteria approximate solution \(S\) with respect to \(\nu_i\) in Lemma 6. Hence, in the next lemma we provide an upper bound on the value of \(\nu_i\) with respect to the value of a \(\mu^*_j\) which later is associated with the optimal \((k, z)\)-clustering cost.

In the analysis in [29], Mettu and Plaxton define a parameter \(r \mathrel{\vcenter{:}}= \ceil{\log_{(1-\beta)}((1-\gamma)/3)}\) and the sets \(F_i\) and \(F_i^r\), for every level \(i \in [0, t]\). Afterwards, the authors utilize these sets in the proofs of their Lemmas \(3.6, 3.7, 3.8, 3.9\), and \(3.10\), in order to conclude their Lemma \(3.11\). We remark that for our analysis we can use the same definitions for the aforementioned sets, and in turn the corresponding lemmas hold here as well. Specifically, we use a version of their Lemma \(3.11\) whose proof ends on the penultimate line and the \((k, z)\)-clustering cost is used, restated as Lemma [lem:lower95bound95opt].⁸ For completeness, we provide a more detailed discussion of these in 7.

4.1.4 Finishing the Proof of [thm:variant95approx]↩︎

By combining the previous observations and lemmas, we can now finish the proof of [thm:variant95approx] which we restate for convenience.

5 Incremental Bicriteria Approximation for \((k, z)\)-Clustering on Graphs↩︎

In this section, we develop an incremental bicriteria approximation algorithm for the \((k, z)\)-clustering problem on graphs undergoing adversarial edge insertions. Our incremental bicriteria approximation algorithm, with high probability, achieves an amortized update time of \(n^{o(1)}\) and maintains a constant-factor bicriteria approximate solution of size at most \(O(k \, \log^3 n \, \log_{1+\epsilon}nW)\). A pseudocode of our incremental bicriteria approximation algorithm is provided in 4, and the result is demonstrated in the following theorem.

Our incremental bicriteria approximation algorithm is an incremental version of the static Algorithm 1, which itself is a variant of the MP-bi algorithm. Throughout the description and analysis of the incremental bicriteria approximation algorithm in 5, we fix a sufficiently large constant \(\alpha \geq 1\) and a small constant \(\beta \in (0, 1)\). In the next two paragraphs, we first describe the information maintained by our incremental bicriteria approximation algorithm, and then outline the properties satisfied by the radii \(\nu_i\).

5.0.0.1 State of the incremental bicriteria approximation algorithm.

Our incremental bicriteria approximation 4 is structured into multiple levels starting from \(0\). The last level of the algorithm is denoted by \(t\), and the value of \(t\) is upper bounded by \(O(\log n)\) throughout the algorithm (see 3). At each level \(i \in [0, t]\), the bicriteria approximation algorithm maintains an execution set \(U_i\), a candidate set \(S_i\), a radius \(\nu_i\), an incremental \((1+\epsilon)\)-approximate SSSP algorithm \(\mathcal{A}_i\) with a super-source attached to \(S_i\), an approximate ball \(B_i\), and a leaking set \(Z_i\).

The incremental algorithm then maintains the bicriteria approximate solution \(S \coloneq \bigcup_{i=0}^t S_i\), and an assignment \(\sigma: V \to S\) that maps each vertex to a candidate center in \(S\) at a specified distance. The algorithm also uses the temporary leaking set \(Z\), an auxiliary set that essentially stores the pending leaked vertices to be assigned to some leaking sets \(Z_i\) (see Lines [algline:leaking95Z], [algline:count95new95for95Zi], [algline:leaking95Zi], and [algline:rem95Zi95from95Z] in 4).

5.0.0.2 Properties of the radii.

For efficiency reasons, the values of the radii \(\nu_i\) (where \(0 \leq i \leq t\)) satisfy three properties over the course of the algorithm. (1) The first property is that the value of each radius \(\nu_i\) is a power of \((1+\epsilon)\). Hence, the number of possible values of a radius \(\nu_i\) is reduced to \(\log_{1+\epsilon}nW\),⁹ at the cost of an extra factor of \((1+\epsilon)\) in the approximation ratio. (2) The second property is that the value of each radius \(\nu_i\) is non-increasing over time, which means that after an adversarial edge insertion, the value of a specific \(\nu_i\) either decreases or remains the same. As a result, the number of distinct sequences of \(\nu_i\) is reduced from \((\log_{1+\epsilon}nW)^t\) to \(\log_{1+\epsilon}nW \cdot t\). We note that the value of the last level \(t\) may increase due to adversarial edge insertions, resulting in more radii \(\nu_i\). However, the incremental algorithm ensures that \(t = O(\log n)\) throughout its execution.

Furthermore, in order to upper bound the cost of the bicriteria approximate solution, the values of the radii \(\nu_i\) (where \(0 \leq i \leq t\)) satisfy also a third property over the course of the algorithm. (3) The third property is that the order of the values of \(\nu_i\) is non-decreasing (i.e., \(\nu_0 \leq \nu_1 \leq \cdots \leq \nu_t)\). Let us provide a high-level justification for the third property: Consider a vertex \(v \in U_i\) that is within a distance of \(\nu_i\) from the candidate set \(S_i\). Assume that after an adversarial edge insertion, the vertex \(v\) moves to the next execution set \(U_{i+1}\) and is not within a distance of \(\nu_{i+1}\) from the next candidate set \(S_{i+1}\). Since under edge insertions the distance between \(v\) and \(S_i\) remains at most \(\nu_i\) and \(\nu_i \leq \nu_{i+1}\) by the third property, the vertex \(v\) can be charged a cost of \(\nu_{i+1}\). Therefore using the third property, we can argue that a (leaked) vertex of any execution set \(U_j\) can be charged a cost of \(\nu_j\) (see also [obs:incr95nu95monoton] 17), which in turn helps us to upper bound the approximation ratio of our incremental algorithm. To sum up, our incremental bicriteria approximation algorithm ensures that the following three properties are satisfied throughout its execution:

1. : The value of each radius \(\nu_i\) is a power of \((1+\epsilon)\).

2. : The value of each radius \(\nu_i\) is non-increasing over time.

3. : The order of the values of the radii \(\nu_i\) is non-decreasing (i.e., \(\nu_0 \leq \nu_1 \leq \cdots \leq \nu_t\)).

5.1 Incremental Bicriteria Approximation Algorithm on Graphs↩︎

First we describe the preprocessing phase, and afterwards we describe how to handle adversarial edge insertions. A pseudocode of our incremental bicriteria approximation algorithm is provided in 2 4.

5.1.1 Preprocessing Phase↩︎

The initialization of our incremental bicriteria approximation algorithm mimics the structure of our MP-bi variant 1. During the preprocessing phase, dynamic data structures are also employed, as described in 2.

Since we have to deal with adversarial edge insertions, an incremental \((1+\epsilon)\)-approximate SSSP algorithm \(\mathcal{A}_i\) (from 1) with a super-source attached to \(S_i\) is initialized for every level \(i \in [0, t)\).¹⁰ In Line [line:algassignment] of 2, we denote by \(\delta_u(v)\) the distance estimate from a candidate center \(u \in S_i\) to a vertex \(v \in V\). We remark that even though we cannot access all \(\delta_u(v)\) directly, we can efficiently compute the closest candidate center \(u \in S_i\) to a vertex \(v \in V\) with respect to \(\delta_{S_i}(\cdot)\). This follows from the fact that the incremental \((1+\epsilon)\)-approximate SSSP algorithm \(\mathcal{A}_i\) has access to the first edge of the corresponding approximate shortest path in \(\tilde{O}(1)\) time; such an incremental SSSP \(\mathcal{A}_i\) can be either the deterministic algorithm from 1 or a randomized algorithm against an oblivious adversary (implicitly given in  [50]–[52]). Thus, the assignment in Line [line:algassignment] can be computed properly and efficiently.

The main reason we introduce \(\operatorname{Retain}(\cdot, \cdot)\) (see 7) in 2 and 4 is because we need the following lemma and 13. In turn, these are required for the correctness analysis of the lower bound in [lem:lower95bound95opt], as discussed in 5.2.3.

5.1.2 Adversarial Edge Insertions↩︎

Before describing how our incremental bicriteria approximation algorithm for the \((k, z)\)-clustering problem on graphs handles adversarial edge insertions, we define the \(i\)-th valid radius in order to guarantee that [property95rad953] is satisfied. Recall that \(\operatorname{Ball}[{S_i}, r, \delta_{S_i}] \mathrel{\vcenter{:}}= \{v \in V \mid \delta_{S_i}(v) \leq r\}\) denotes the closed ball of radius \(r\) around \({S_i}\) using the distance estimates \(\delta_{S_i}(\cdot)\).

When an edge \((u^+, v^+)\) is inserted into the graph \(G = (V, E, w)\) from the adversary, the incremental bicriteria approximation algorithm proceeds as follows. Initially, this adversarial edge insertion \((u^+, v^+)\) is forwarded to all the incremental \((1+\epsilon)\)-approximate SSSP algorithms \(\mathcal{A}_i\), where \(0 \leq i < t\). The algorithm then finds the smallest level \(\ell \in [0, t]\) for which the (updated) \(\ell\)-th valid radius \(\hat{\nu}_\ell\) is less than the \(\ell\)-th radius \(\nu_\ell\) (i.e., \(\hat{\nu}_\ell < \nu_\ell\)).¹² This step is implemented through the function First-Level-Decrease\(()\) (see Lines [algline:func95first95lvl95decr] and [algline:first95level95decr] in 4).

Next, the function Update-DS-Rad-Decr(\(\ell\)) is called within the function First-Level-Decrease\(()\), which updates the data structures at level \(\ell\). In the function Update-DS-Rad-Decr(\(\ell\)), the incremental algorithm updates the \(\ell\)-th radius \(\nu_\ell\) to \(\hat{\nu}_\ell\) and the \(\ell\)-th approximate ball \(B_\ell\) to an arbitrary subset of \(\operatorname{Ball}[S_\ell, \hat{\nu}_\ell, \delta_{S_\ell}] \cap U_\ell\) with size \(\ceil{\beta |U_\ell|}\) (in Lines [algline:set95nu] and [algline:incr95construct95Bi95update] of 4).¹³ For each vertex \(v \in B_\ell\), the algorithm updates its assignment \(\sigma(v)\) to its nearest candidate center in \(S_\ell\) with respect to \(\delta_{S_\ell}(\cdot)\) (in Line [algline:v95to95sigma] of 4). The incremental algorithm then assigns the temporary leaking set \(Z\) as the union of the \(\ell\)-th leaking set \(Z_\ell\) and the vertices that were in the old \(\ell\)-th approximate ball but are not in the updated \(\ell\)-th approximate ball \(B_\ell\) (in Line [algline:leaking95Z] of 4). Eventually, the algorithm empties the \(\ell\)-th leaking set \(Z_\ell\) (in Line [algline:leaking95Zi95empty] of 4).

Once the function First-Level-Decrease\(()\) has finished, the algorithm updates the \((\ell+1)\)-th execution set \(U_{\ell+1}\) to \(U_\ell \setminus B_\ell\). In turn, the incremental algorithm must verify whether the value of the \((\ell+1)\)-th radius \(\nu_{\ell+1}\) should also decrease. Note that as the \((\ell+1)\)-th execution set \(U_{\ell+1}\) may change, the current \((\ell+1)\)-th candidate set \(S_{\ell+1}\) which was sampled from the old \((\ell+1)\)-th execution set, may no longer be a good representative in the new \((\ell+1)\)-th execution set \(U_{\ell+1}\). To that end, the algorithm proceeds with the Resampling Phase in the updated \((\ell+1)\)-th execution set \(U_{\ell+1}\), as follows. Since \(\ell\) denotes the smallest level at which the corresponding \(\ell\)-th radius \(\nu_\ell\) is decreased, let \(i \mathrel{\vcenter{:}}= \ell + 1\) represent the subsequent levels starting at level \(\ell + 1\).

5.1.2.1 Resampling Phase.

First, a supporting candidate set \(\tilde{S}_i\) is constructed by sampling each vertex of the new \(i\)-th execution set \(U_i\) independently with probability \(\min\Big(\frac{\alpha k \log n}{|U_i|}, 1\Big)\). Second, the incremental algorithm adds the \(i\)-th supporting candidate set \(\tilde{S}_i\) to the \(i\)-th candidate set \(S_i\), and restarts the \(i\)-th incremental \((1+\epsilon)\)-approximate SSSP algorithm \(\mathcal{A}_i\) with a super-source attached to the updated \(i\)-th candidate set \(S_i\).¹⁴ Next, the algorithm computes the \(i\)-th valid radius \(\hat{\nu}_i\), using the updated \(i\)-th candidate set \(S_i\) and the updated distance estimates \(\delta_{S_i}(\cdot)\) (see Lines [algline:check95if95nu95decreases952] and [algline:set95hat95nu952] in 4). The incremental algorithm then proceeds based on whether the (updated) \(i\)-th valid radius \(\hat{\nu}_i\) is less than the \(i\)-th radius \(\nu_i\), as follows:

• If \(\hat{\nu}_i < \nu_i\), then the algorithm updates the data structures as described previously with further modifications (see the function Update-DS-Rad-Decr(\(i\)) in Lines [algline:func95update95ds95rad95decr] and [algline:update95ds95rad95decr952] of 4). In particular, the incremental algorithm updates the \(i\)-th radius \(\nu_i\) to \(\hat{\nu}_i\) and the \(i\)-th approximate ball \(B_i\) to an arbitrary subset of \(\operatorname{Ball}[S_i, \hat{\nu}_i, \delta_{S_i}] \cap U_i\) with size \(\ceil{\beta |U_i|}\) (in Lines [algline:set95nu] and [algline:incr95construct95Bi95update] of 4).¹⁵ For each vertex \(v \in B_i\), the algorithm updates its assignment \(\sigma(v)\) to its nearest candidate center in \(S_i\) with respect to \(\delta_{S_i}(\cdot)\). Subsequently, the incremental algorithm adds to the temporary leaking set \(Z\) both the \(i\)-th leaking set \(Z_i\) and the vertices that were in the old \(i\)-th approximate ball but are not in the updated \(i\)-th approximate ball \(B_i\) (see Figure 3). The algorithm then empties the \(i\)-th leaking set \(Z_i\) and updates the \((i+1)\)-th execution set \(U_{i+1}\) to \(U_i \setminus B_i\).

• Otherwise if \(\hat{\nu}_i \geq \nu_i\), then the algorithm removes from the \(i\)-th approximate ball \(B_i\) all vertices that no longer belong to the \(i\)-th execution set \(U_i\).¹⁶ Observe also that for a level \(j: 0 \leq j < i\), some vertices that belonged to the old \(j\)-th approximate ball before the adversarial edge insertion, may no longer belong to the new \(j\)-th approximate ball \(B_j\) after the adversarial edge insertion. Note that some of these vertices have been added to the temporary leaking set \(Z\). Subsequently, the incremental algorithm adds to the \(i\)-th leaking set \(Z_i\) an arbitrary subset of the temporary leaking set \(Z\), ensuring that \(Z_i \subseteq U_i\) and \(|Z_i| = \ceil{\beta |U_i|} - |B_i|\) (see Lines [algline:Bi95subset95Ui], [algline:count95new95for95Zi], and [algline:leaking95Zi] in 4).¹⁷ The algorithm then removes from the temporary leaking set \(Z\) the subset of \(Z\) that entered the \(i\)-th leaking set \(Z_i\) (see Line [algline:rem95Zi95from95Z] in 4) and updates the \((i+1)\)-th execution set \(U_{i+1}\) to \(U_i \setminus (B_i \cup Z_i)\).

Afterwards, the incremental algorithm increases \(i\) by one (i.e., moves to the next level), and continues with the Resampling Phase in the updated \(i\)-th execution set \(U_i\) (for the updated level \(i\)) as described earlier. The Resampling Phase terminates when the size of the current \(i\)-th execution set \(U_i\) is at most \(\alpha k \log n\). Then, the algorithm updates the value of the last level \(t\) to the final value of \(i\) (see Line [algline:t95last95level] in 4). Finally, as a concluding step for the adversarial edge insertion \((u^+, v^+)\) into the graph \(G\), the incremental bicriteria approximation algorithm trivially updates the data structures at level \(t\) (in Line [algline:last95level95assign] of 4) and assigns the maintained bicriteria approximate solution \(S\) as \(\bigcup_{i=0}^t S_i\) (in Line [algline:assign95solution] of 4).

5.1.2.2 On the computation of \(\tilde{\nu}_i\).

We emphasize that the value \(\tilde{\nu}_i\) in Lines [algline:check95if95nu95decreases951] and [algline:check95if95nu95decreases952] of 4 can be computed during the update procedure of the \(i\)-th incremental \((1+\epsilon)\)-approximate SSSP algorithm \(\mathcal{A}_i\). This is achieved by extending \(\mathcal{A}_i\) to track the necessary quantities within its update procedure, without incurring additional asymptotic cost. The reason this is possible is that, based on 1, \(\mathcal{A}_i\) detects and reports a change whenever the distance estimate \(\delta_{S_i}(v)\) is updated for a vertex \(v \in V\). As a result, the cost of maintaining \(\tilde{\nu}_i\) is included in the update time of \(\mathcal{A}_i\).¹⁸

5.2 Analysis of the Incremental Bicriteria Approximation Algorithm↩︎

When an edge is inserted into the graph \(G = (V, E, w)\) from the adversary, multiple pairwise distances between vertices may change significantly, requiring the incremental algorithm to update the maintained data structures. To distinguish between the states of the input graph \(G\) and our incremental algorithm before and after an adversarial edge insertion, we use \(\text{(old)}\) as a superscript for the state before the edge insertion, and we omit the \(\text{(old)}\) superscript for the state after the edge insertion.¹⁹

Our goal in this section is to prove Theorem [thm:incr95alg], by analyzing the incremental bicriteria approximation 4. The analysis is divided into four subsections, as outlined below. First, in 5.2.1 we analyze the amortized update time of our incremental bicriteria approximation algorithm. Next, in 5.2.2 we derive an upper bound on the cost of the maintained bicriteria approximate solution \(S\). Then, in 5.2.3 we establish results concerning a lower bound on the optimal \((k, z)\)-clustering cost which is associated with the upper bound. Finally, in 5.2.4 we provide an upper bound on the size of the bicriteria approximate solution and we conclude the proof of Theorem [thm:incr95alg].

5.2.1 Analysis of the Update Time↩︎

The next corollary establishes that the incremental bicriteria approximation 4 maintains \(O(\log n)\) levels throughout its execution.

5.2.2 Analysis of the Upper Bound↩︎

The next lemma provides an upper bound on the \((k, z)\)-clustering cost of both the bicriteria approximate solution \(S\) and the bicriteria approximate assignment \(\sigma\).

5.2.3 Results Regarding the Lower Bound↩︎

We continue with the lower bound on the optimal \((k, z)\)-clustering cost under adversarial edge insertions, adjusting the analysis in 4.1.3 (which in turn adapts the analysis in [29]). Similarly to the analysis in 4.1, we fix a positive real number \(\gamma\) such that \(\beta < \gamma < 1\). We also define \(\nu^*_i\) and \(\mu^*_i\) for a fixed level \(i \in [0, t]\), as described in Definition 9 and Definition 10 respectively.²⁷

Recall that in the definition above, the vertices of \(U_i\) that are exactly at distance \(\mu_{i}^*\) from \(X_i\) belong to both \(\operatorname{Ball}[X_i, \mu_i^*]\cap U_i\) and \(U_i\setminus \operatorname{Ball}(X_i, \mu_i^*)\). At this point in the analysis, we would like to use [lem:nu602mu] to establish a relationship between \(\nu_i^*\) and \(\mu_i^*\). However, [lem:nu602mu] is applicable only to the static setting, whereas in the incremental setting the execution sets and candidate sets are subject to changes. To that end, we first provide an extension of [lem:nu602mu] demonstrated as [lem:nu602mu951], and then we establish an ‘incremental’ relationship between \(\nu_i^*\) and \(\mu_i^*\) in 20 utilizing the fact that the adversary is oblivious. The proof of [lem:nu602mu951] is very similar to that of [lem:nu602mu], and both proofs are deferred to 7.

Even though 4 provides an upper bound for \(\tilde{\nu}_{i}\), recall that the incremental Algorithm 4 uses the radius \(\nu_i\) computed in Line [algline:set95nu], which is at least \(\tilde{\nu}_{i}\). In particular, we upper bound the cost of the bicriteria approximate solution \(S\) with respect to \(\nu_i\) in Lemma 18. Hence, in the next lemma we provide an upper bound on the value of the \(i\)-th radius \(\nu_i\) in terms of the value of some \(\mu^*_j\) with \(j\leq i\), which later is associated with the optimal \((k, z)\)-clustering cost.

Notably, we can lower bound the optimal \((k, z)\)-clustering cost with respect to the \(\mu_i^*\) values by reusing Lemma [lem:lower95bound95opt], which we restate for convenience. The reason Lemma [lem:lower95bound95opt] continues to hold after every adversarial edge insertion in the incremental setting is as follows. After every adversarial edge insertion, the proof of Lemma [lem:lower95bound95opt] (given in 7) can be repeated with two modifications: in [clm:rel95Y95Fi] we replace 6 by its incremental equivalent 10, and in [clm:Fi95shrink] we replace 3 by its incremental counterpart 13. The reader may also find it helpful to refer to the discussion in 4.1.3 just before Lemma [lem:lower95bound95opt]. Recall that \(\gamma \in (\beta, 1)\) is the parameter used in 10.

5.2.4 Size of the Bicriteria Approximate Solution and Proof of Theorem [thm:incr95alg]↩︎

By combining the previous observations and lemmas, we can now finish the proof of [thm:incr95alg] which we restate for convenience.

6 From Bicriteria Approximation to \((k, z)\)-Clustering on Incremental Graphs↩︎

Thus far, our incremental bicriteria approximation 4 of [thm:incr95alg] efficiently maintains an \((O(1), O(\log^3 n \, \log_{1+\epsilon}nW))\)-bicriteria approximate solution to the \((k,z)\)-clustering problem on a graph undergoing edge insertions. Recall that by 3, this means that 4 maintains a subset of vertices \(S \subseteq V\) such that \(\operatorname{cost}^z(S) \leq O(\text{OPT})\) and \(|S| \leq O(k \log^3 n \, \log_{1+\epsilon}nW)\). Our goal though is to compute a constant-factor approximate solution \(C\) for the \((k, z)\)-clustering problem (see 1), and thus the output \(C\) must consist of at most \(k\) vertices. In other words, we want to maintain a subset of vertices \(C \subseteq V\) such that \(\operatorname{cost}^z(C)\leq O(\text{OPT})\) and \(|C| \leq k\).

In this section, we describe an efficient incremental reduction algorithm that reduces the size of an \((O(1), O(\log^3 n \, \log_{1+\epsilon}nW))\)-bicriteria approximate solution \(S\) by converting it into a constant-factor approximate \((k, z)\)-clustering solution \(C\) in a graph that undergoes edge insertions. To achieve this, we maintain a \((k, z)\)-clustering solution \(C\) over the bicriteria approximate solution \(S\), using weights on \(S\) determined by the corresponding bicriteria approximate assignment \(\sigma\).

We remark that our [thm:bicr95to95kzclustering] (the incremental reduction algorithm) is an adaptation of a theorem in [29], [55] (its variant appears as 27) in the incremental graph setting. The following definitions are used to analyze the total update time in [thm:bicr95to95kzclustering]. Notice that in 12, the value of \(\sigma_\text{inc}(V)\) is equal to the total number of batches of new vertices entering the image of \(\sigma\). Hence, whenever \(|\sigma_\text{max}(V)|\) increases in a single update due to multiple new vertices, \(\sigma_\text{inc}(V)\) increases by one.

A pseudocode of our incremental reduction algorithm is provided in 5. Our incremental reduction algorithm for the \((k,z)\)-clustering problem (in [thm:bicr95to95kzclustering]) uses the fully dynamic spanner algorithm of Baswana, Khurana, and Sarkar [49]. Their initial result is for unweighted graphs, but as the authors mention in their Remark 1.2 in [49], it can be extended to weighted graphs.

Note that an incremental spanner (i.e., non-increasing distances) would be sufficient; however, the fully dynamic spanner algorithm of 23 is already suitable in our context. The expected guarantees can be turned into high probability guarantees by running \(\Theta(\log n)\) copies of the algorithm in parallel; see [56] for more details. The incremental reduction algorithm also utilizes the static \((k, z)\)-clustering algorithm of Dupre la Tour and Saulpic [32].

At a high level, we maintain the \((k, z)\)-clustering solution \(C\) over the bicriteria approximate solution \(S\), using weights on \(S\) derived from the bicriteria approximate assignment \(\sigma\). Hence, the input graph instance contains both edge and vertex weights, and the static \((k, z)\)-clustering algorithm should be able to work with vertex weights in our context. The algorithm by Dupre la Tour and Saulpic [32] is a simplification of the algorithm by Mettu and Plaxton [28].³⁰ Even though the authors in [32] present a version without vertex weights, the authors in [28] present a version with weights on points. Thus, it is not surprising that the static \((k, z)\)-clustering algorithm of 24 can be generalized to handle vertex weights. For completeness, we provide a more detailed discussion of this in 8.

Based on the discussion in 8, we can safely assume for the rest of the paper that the static \((k, z)\)-clustering algorithm of 24 works on weighted \((k, z)\)-clustering instances, as defined in [def:wgt95k95median]. The randomization in [thm:bicr95to95kzclustering] arises from the randomization in 23 24; replacing the randomized subroutines with deterministic counterparts would yield a deterministic version of [thm:bicr95to95kzclustering].

6.0.0.1 Adversarial updates.

Our aim is to combine the incremental bicriteria approximation 4 with the incremental reduction 5. Hence, the output \((\alpha, \beta)\)-bicriteria approximate assignment \(\sigma\) of 4 becomes the input \((\alpha, \beta)\)-bicriteria approximate assignment \(\sigma\) of 5. The assignment \(\sigma\) in 4 can be modified due to an adversarial edge insertion into the graph \(G\), making it a dynamic assignment in [thm:bicr95to95kzclustering].

Since our incremental reduction algorithm is given as input a dynamic bicriteria approximate assignment, one type of adversarial update consists of modifications to the assignment \(\sigma\). The other type of adversarial update involves edge insertions into the input graph \(G\), where each adversarial edge insertion can trigger a batch of distance decreases between vertices in \(G\).

Note that an efficient combination of 4 and 5, requires that both (1) the total number of vertices that have ever belonged to the image of the dynamic assignment \(\sigma\) (i.e., \(|\sigma_\text{max}(V)|\)) and (2) the total number of batches of new vertices entering \(\sigma_\text{max}(V)\) (i.e., \(\sigma_\text{inc}(V)\)) remain bounded. For efficiency reasons, we employ the approximate distance estimates from incremental \((1+\epsilon)\)-approximate SSSP algorithms and perform lazy updates by maintaining distances as powers of \((1+\epsilon)\).

6.0.0.2 State of the reduction algorithm.

Our incremental reduction 5 maintains a dynamic \((\alpha, \beta)\)-bicriteria approximate solution \(S \mathrel{\vcenter{:}}= \sigma(V)\), which is the image of the dynamic \((\alpha, \beta)\)-bicriteria approximate assignment \(\sigma\) from the input.³¹ For every vertex \(s \in S\), the reduction algorithm maintains an incremental \((1+\epsilon)\)-approximate SSSP algorithm \(\mathcal{A}_s\) providing distance estimates \(\delta_s(\cdot)\). In turn, the reduction algorithm maintains a complete subgraph \(H \mathrel{\vcenter{:}}= (S, S \times S, w_H)\) with edge and vertex weights, specified as follows:

• Each vertex \(s \in S\) belongs to the vertex set of \(H\), and the vertex weight \(\operatorname{wt}(s)\) is equal to \(|\sigma^{-1}(s)|\). In other words, the vertex weight of \(s\) in \(H\) is the number of vertices mapped to \(s\) under the assignment \(\sigma(\cdot)\).

• For every pair of vertices \(x, y \in S\), the edge \((x, y)\) belongs to the edge set of \(H\) with an edge weight \(w_H(x, y)\) equal to \(\min(\delta_x(y), \delta_y(x))\), rounded up to the nearest power of \((1 + \epsilon)\).

The incremental reduction algorithm then applies the dynamic spanner algorithm \(\mathcal{SP}\) of 23 on the subgraph \(H\) to obtain an edge-sparsified graph \(\tilde{H}\). Finally, the reduction algorithm runs the static \((k, z)\)-clustering algorithm \(\mathcal{CL}\) of 24 on the weighted \((k, z)\)-clustering instance \((\tilde{H}, k, z, \operatorname{wt})\), producing a \((k, z)\)-clustering solution \(C\).

6.1 Adversarial Edge Insertions and Assignment Modifications↩︎

In the next two paragraphs, we first describe how our incremental reduction algorithm processes an adversarial edge insertion into the graph \(G\), and then how it processes a batch of modifications to the \((\alpha, \beta)\)-bicriteria approximate assignment \(\sigma\). We remark that in fact, each adversarial edge insertion into the graph \(G\) can trigger a batch of distance decreases between vertices in \(G\) alongside a batch of modifications to \(\sigma\).

6.1.0.1 Edge insertion into \(G\).

When an edge \((u, v)\) is inserted into the graph \(G = (V, E, w)\) from the adversary, the incremental reduction algorithm proceeds as follows. Initially, this edge insertion \((u, v)\) is forwarded to all the incremental \((1+\epsilon)\)-approximate SSSP algorithms \(\mathcal{A}_s\), where \(s \in S\). Based on 1, the incremental \((1+\epsilon)\)-approximate SSSP algorithm \(\mathcal{A}_s\) reports a change whenever the distance estimate \(\delta_s(x)\) is updated for a vertex \(x \in V\). After the adversarial insertion of the edge \((u, v)\) into the graph \(G\), let \(\Delta_S\) be the set containing all the pairs of vertices \((x, y) \in S \times S\) such that the value of the distance estimate \(\delta_x(y)\) becomes less than \(\frac{w_H(x, y)}{1+\epsilon}\).

Next, for every pair of vertices \((x, y) \in \Delta_S\), the incremental reduction algorithm updates the edge weights \(w_H(x, y)\) and \(w_H(y, x)\) to \(\min(\delta_{x}(y),\delta_{y}(x))\), rounding them up to the nearest power of \((1+\epsilon)\). Let \(B \mathrel{\vcenter{:}}= \big\{\big(x, y, w_H(x, y)\big) \mid (x, y) \in \Delta_S \text{ or } (y, x) \in \Delta_S\big\}\) be the batch of distance decreases. The reduction algorithm then forwards the batch \(B\) of distance decreases to the dynamic spanner algorithm \(\mathcal{SP}\) from 23,³² which runs on \(H\) and maintains the edge-sparsified graph \(\tilde{H}\).

6.1.0.2 Modifications to the assignment \(\sigma\).

Let \(R_S\) be the set containing all vertices \(s \in V\) for which the preimage \(\sigma^{-1}(s)\) is modified. For every vertex \(s \in R_S\) that already belongs to the dynamic \((\alpha, \beta)\)-bicriteria approximate solution \(S\), the reduction algorithm updates only its vertex weight \(\operatorname{wt}(s)\) to \(|\sigma^{-1}(s)|\).

For every vertex \(s \in R_S\) that does not belong to the dynamic \((\alpha, \beta)\)-bicriteria approximate solution \(S\), the incremental reduction algorithm proceeds as follows:

1. First, the reduction algorithm adds \(s\) to \(S\) and to the vertex set of \(H\), and sets its vertex weight \(\operatorname{wt}(s)\) to \(|\sigma^{-1}(s)|\).

2. Second, the reduction algorithm initializes an incremental \((1+\epsilon)\)-approximate SSSP algorithm \(\mathcal{A}_s\) providing distance estimates \(\delta_s(\cdot)\). Then for every vertex \(x \in S\), the edge weights \(w_H(s, x)\) and \(w_H(x, s)\) are set to \(\min(\delta_s(x), \delta_x(s))\), rounded up to the nearest power of \((1+\epsilon)\).

Next, if at least one new vertex is added to \(S\) (i.e., \(|\sigma_\text{max}(V)|\) of 11 increases) then the reduction algorithm restarts the dynamic spanner algorithm \(\mathcal{SP}\) on the subgraph \(H\), producing a new edge-sparsified graph \(\tilde{H}\). Otherwise all vertices in \(R_S\) already belong to \(S\), and the dynamic spanner algorithm \(\mathcal{SP}\) maintains the same edge-sparsified graph \(\tilde{H}\).

At the end of each adversarial update, the incremental reduction algorithm runs the static \((k, z)\)-clustering algorithm \(\mathcal{CL}\) of 24 on the updated weighted \((k, z)\)-clustering instance \((\tilde{H}, k, z, \operatorname{wt})\), producing the maintained \((k, z)\)-clustering solution \(C\).

6.1.0.3 Implementation of Line [algline:Delta95S].

We emphasize that the set \(\Delta_S\) in Line [algline:Delta95S] of 5 can be computed during the update procedure of the incremental \((1+\epsilon)\)-approximate SSSP algorithm \(\mathcal{A}_x\). This is achieved by extending \(\mathcal{A}_x\) to track the necessary quantities within its update procedure, without incurring additional asymptotic cost.

6.2 Analysis of the Incremental Reduction Algorithm↩︎

Our goal in this section is to prove Theorem [thm:bicr95to95kzclustering], by analyzing the incremental reduction 5. We remind the reader that the reduction algorithm maintains weighted \((k, z)\)-clustering instances \(\mathcal{K} \mathrel{\vcenter{:}}= (H, k, z, \operatorname{wt})\) and \(\mathcal{\tilde{K}} \mathrel{\vcenter{:}}= (\tilde{H}, k, z, \operatorname{wt})\) (edge-sparsified) induced by the dynamic bicriteria approximate solution \(S = \sigma(V)\) in the incremental graph \(G\). To distinguish the cost of a \((k, z)\)-clustering solution \(C\) in \(\mathcal{K}\) from its cost in \(G\), we use the notation \(\operatorname{cost}^z_{\operatorname{wt}}(C, \mathcal{K})\) and \(\operatorname{cost}^z(C, G)\) respectively.

6.2.1 Approximation Ratio↩︎

Let \(\rho_1 = O(1)\) denote the constant in the approximation ratio of the dynamic spanner algorithm \(\mathcal{SP}\) from 23, and \(\rho_2 = O(1)\) denote the constant in the approximation ratio of the static \((k, z)\)-clustering algorithm \(\mathcal{CL}\) from 24.

The following lemma is a variant of a theorem from [29], [55] usually stated for point sets in metric spaces; the same statement holds naturally for graphs, and we extend it to apply to our edge-sparsified graph \(\tilde{H}\). Essentially, we use it to argue that it suffices to solve the weighted \((k, z)\)-clustering instance induced by the dynamic bicriteria approximate assignment \(\sigma\). The proof of 27 follows from 28 29.

6.2.2 Total Update Time and Proof Completion of [thm:bicr95to95kzclustering]↩︎

6.3 Putting Everything Together↩︎

In this section, we combine the tools we developed in order to obtain our result for the \((k,z)\)-clustering problem on incremental graphs. The next lemma shows that the dynamic spanner algorithm \(\mathcal{SP}\) is restarted only \(\tilde{O}(1)\) times in total.

6.3.0.1 Disconnected graphs.

Although our arguments are simpler when the input graph \(G\) is connected, the same guarantees hold for disconnected graphs as well. In particular, the input graph \(G\) may be initially empty (i.e., without any edges). In this paragraph, we explain in more detail how our incremental algorithm handles disconnected graphs.

First, observe that in our incremental bicriteria approximation 4 the \(i\)-th valid radius \(\hat{\nu}_i\) depends on the value of \(\tilde{\nu}_i\) determined at Line [algline:check95if95nu95decreases951] or Line [algline:check95if95nu95decreases952] in 4 (see also 8), where \(i \in [0, t)\) is a fixed level. When the graph \(G\) is disconnected, it is possible that \(\tilde{\nu}_i\) is undefined, since there may be no such ball of size at least \(\beta |U_i|\) (even if \(\tilde{\nu} = \infty\)). In this case, based on 4 and 10, the corresponding \(\mu_i^*\) is also \(\infty\).³⁴ Since [lem:lower95bound95opt] allows us to lower bound the optimal \((k, z)\)-clustering cost using the \(\mu_i^*\) values after each adversarial edge insertion in the incremental setting, we conclude that the optimal \((k, z)\)-clustering cost is infinite. Therefore, whenever the value of some \(\tilde{\nu}_i\) is \(\infty\), the incremental algorithm can safely report that \(\text{OPT}= \infty\).

Another subtle situation concerns the \(i\)-th supporting candidate set \(\tilde{S}_i\), the \(i\)-th candidate set \(S_i\), and the restart of the \(i\)-th incremental \((1+\epsilon)\)-approximate SSSP algorithm \(\mathcal{A}_i\) at Line [algline:sssp95update] in 4, where \(i \in [0, t)\) is a fixed level. As explained in 22, each isolated vertex must be a center, as otherwise the cost of the solution would be infinite. Consequently, each vertex can be given the opportunity to be sampled once it has an incident edge. To avoid restarting \(\mathcal{A}_i\) every time a new vertex is sampled in this “lazy” way, we simply extend the super-source attached to \(S_i\) by adding the corresponding new zero-weight edges. In other words, we simply add a zero-weight edge from the super-source to each newly sampled candidate center.³⁵

Finally, the static \((k, z)\)-clustering algorithm in [32] can be adapted to work with disconnected graphs. Another way to transform any static \((k, z)\)-clustering algorithm for connected graphs to handle disconnected graphs is as follows. There must be at most \(k\) connected components, since otherwise the cost of the solution is infinite. Hence, we can connect the \(O(k)\) components with sufficiently large-weight edges (e.g., weight equal to \(n \cdot (nW) + 1\)).³⁶ Specifically, we order the connected components and add an edge of sufficiently large weight between the \(i\)-th and the \((i+1)\)-th connected component. Then the new instance is a connected graph whose set of (\(O(1)\)-approximate) solutions remains unchanged. As a result, our incremental algorithm can handle disconnected graphs as well.

Acknowledgments↩︎

We would like to thank Aditi Dudeja for taking the time to meet and engage in thoughtful conversations in Salzburg.

Appendix↩︎

7 Missing Proofs↩︎

In this section, we prove the lemmas whose proofs were omitted from the main body of the paper.

7.1 Proof of [lem:lower95bound95opt]↩︎

We first prove a series of claims, and then use them to establish [lem:lower95bound95opt]. The analysis follows a similar structure to that presented in [29].

Consider an arbitrary fixed subset of vertices \(X \subseteq V\) of size at most \(k\). For each level \(i \in [0, t]\), we define \(F_i \mathrel{\vcenter{:}}= \{v \in U_i \mid \operatorname{dist}(v, X) \geq \mu^*_i\}\), \(F_i^\lambda \mathrel{\vcenter{:}}= F_i \setminus \bigcup_{j>0} F_{i+j\lambda}\), and \(M_{i,\lambda} \mathrel{\vcenter{:}}= \{j\in [0, t]\mid j \equiv i\mod \lambda\}\). Recall that \(t\) denotes the last level of the algorithm.

We extend the definition of \(\operatorname{cost}^z(\cdot)\) to pairs of vertex sets by defining \(\operatorname{cost}^z(X, Y) \mathrel{\vcenter{:}}= \sum_{v \in Y} \operatorname{dist}(v, X)^z\), so that it gives the cost of \(X\) evaluated on \(Y\).

Recall that \(r\mathrel{\vcenter{:}}= \ceil{\log_{(1-\beta)}((1-\gamma)/3)}\) and \(0 < \beta < \gamma < 1\) are small constants. We show that for any level \(i\), the set \(F_{i+r}\) has size at most one third of \(F_i\), and thus \(F_i^r\) has size at least half of \(F_i\).

8 Extending 24 to vertex weights↩︎

The static \((k, z)\)-clustering algorithm of Dupre la Tour and Saulpic [32] defines a function \(\text{Value}(\operatorname{Ball}[x, r]) \mathrel{\vcenter{:}}= \lvert\operatorname{Ball}[x, r]\rvert \cdot r^z\), for a vertex \(x \in V\), a positive real number \(r\), and a constant \(z \geq 1\). In fact, the authors show that an approximation of \(\lvert\operatorname{Ball}[x, r]\rvert \cdot r^z\) suffices. In particular, \(\text{Value}(\operatorname{Ball}[x, r])\) should satisfy the following inequalities (where \(\lambda \geq 5\) is a constant): \[\lvert\operatorname{Ball}[x, r]\rvert \cdot \frac{r^z}{3} \;\leq\; \text{Value}(\operatorname{Ball}[x, r]) \;\leq\; \lvert\operatorname{Ball}[x, \lambda r]\rvert \cdot 3 r^z.\] To generalize the arguments to work with vertex weights \(\operatorname{wt}(\cdot)\), the function \(\text{Value}(\cdot)\) should be generalized to \(\text{Value}_{\operatorname{wt}}(\operatorname{Ball}[x, r]) \mathrel{\vcenter{:}}= \operatorname{wt}(\operatorname{Ball}[x, r]) \cdot r^z\), where \(\operatorname{wt}(\operatorname{Ball}[x, r]) \mathrel{\vcenter{:}}= \sum_{v \in \operatorname{Ball}[x, r]} \operatorname{wt}(v)\). Similarly, it suffices that \(\text{Value}_{\operatorname{wt}}(\operatorname{Ball}[x, r])\) satisfy the following inequalities (where \(\lambda \geq 5\) is a constant): \[\operatorname{wt}(\operatorname{Ball}[x, r]) \cdot \frac{r^z}{3} \;\leq\; \text{Value}_{\operatorname{wt}}(\operatorname{Ball}[x, r]) \;\leq\; \operatorname{wt}(\operatorname{Ball}[x, \lambda r]) \cdot 3 r^z.\] Equipped with this definition of \(\text{Value}_{\operatorname{wt}}(\operatorname{Ball}[x, r])\), the same arguments presented in Appendix A of [32] can be repeated for the weighted \((k, z)\)-clustering problem.

Furthermore, the static \((k, z)\)-clustering algorithm of Dupre la Tour and Saulpic [32] employs the near-linear time algorithm of Cohen [58] in order to efficiently compute the values \(\text{Value}_{\operatorname{wt}}(\operatorname{Ball}[x, r])\). Since the algorithm in [58] works with vertex weights, 24 can be extended to handle vertex weights as well.

References↩︎

---

1. European University of Rome, Italy. This research was partially conducted when the author was a postdoc at the University of Salzburg.↩︎

2. Department of Computer Science, University of Salzburg, Salzburg, Austria. This work is supported by the Austrian Science Fund (FWF): P 32863-N. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 947702).↩︎

3. Department of Computer Science, University of Warwick, Coventry, England. This research was partially conducted when the author was a PhD student at the University of Salzburg. Antonis Skarlatos is funded by the European Union (ERC grant, DYNALP, 101170133). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.↩︎

4. The notation \(\tilde{O}(\cdot)\) hides polylogarithmic factors in \(nW\).↩︎

5. Recall that in a \(\rho\)-metric space, the triangle inequality may be violated by a factor of \(\rho\).↩︎

6. We assume that the weights are at least \(1\) and are upper bounded by a polynomial in \(n\). This can be achieved by rescaling all the weights.↩︎

7. Note that we can assume \(n > 1\), as otherwise the \((k,z)\)-clustering instance can be trivially solved.↩︎

8. In the proof of Lemma \(3.11\) in [29], there is a small typo in the definition of \(\ell\). Specifically, the parameter \(\mu_i\) is missing from the inner sum \(\sum_{i \in G_{j, r}}\).↩︎

9. Recall that \(W\) is the maximum weight of an edge, and thus \(nW\) is the maximum possible distance between two vertices in \(G\).↩︎

10. Namely, we introduce a fake root \(s\) and add an edge \((s, v)\) of zero weight, for every candidate center \(v \in S_i\). Then, the incremental \((1+\epsilon)\)-approximate SSSP algorithm is executed with source \(s\).↩︎

11. For the definition of the \(0\)-th valid radius, we set \(\nu_{-1} = 0\).↩︎

12. If no such level \(\ell\) exists, then the incremental bicriteria approximation algorithm does nothing.↩︎

13. In the analysis (see 12) we show that \(\lvert\operatorname{Ball}[S_\ell, \hat{\nu}_\ell, \delta_{S_\ell}] \cap U_\ell\rvert \geq \ceil{\beta |U_\ell|}\), and thus there exists such a subset of size \(\ceil{\beta |U_\ell|}\).↩︎

14. When we say in Line [algline:sssp95update] of 4 “\(\mathcal{A}_i\) provides distance estimates \(\delta_u(\cdot)\) for all \(u \in S_i\)”, we mean the nearest candidate center \(u \in S_i\) to a vertex \(v \in V\) with respect to \(\delta_{S_i}(v)\).↩︎

15. In the analysis (see 12) we show that \(\lvert\operatorname{Ball}[S_i, \hat{\nu}_i, \delta_{S_i}] \cap U_i\rvert \geq \ceil{\beta |U_i|}\), and thus there exists such a subset of size \(\ceil{\beta |U_i|}\).↩︎

16. A vertex that belonged to the old \(i\)-th execution set is removed from the current \(i\)-th execution set \(U_i\) when it enters a previous \(j\)-th approximate ball \(B_j\) at some level \(j < i\).↩︎

17. In the analysis (see 13 [clm:new95vert95in95Z]) we show that such a subset of the temporary leaking set \(Z\) exists.↩︎

18. Observe that in Line [algline:check95if95nu95decreases951] of 4, the value \(\tilde{\nu}_t\) at the last level \(t\) is trivially zero.↩︎

19. Whenever we say “after an (adversarial) edge insertion”, we mean after the algorithm has completed all updates to its data structures.↩︎

20. Note that for the corner case where \(\ell\) equals \(t\), nothing changes.↩︎

21. Notice that in Line [algline:next95exec95set951], we have \(Z_i = \emptyset\).↩︎

22. For \(i=0\), we choose \(|U_{-1}|\) so that \(|U_0| = |U_{-1}| - \ceil{\beta |U_{-1}|}\).↩︎

23. Here, \(Z\) refers to the current temporary leaking set at level \(i\), rather than the updated set obtained after Line [algline:rem95Zi95from95Z] in 4. More precisely, it refers to \(Z^\text{(old)}\), but we write \(Z\) for ease of reading.↩︎

24. Note that we can assume \(n > 1\), as otherwise the \((k, z)\)-clustering instance can be trivially solved.↩︎

25. Notice that each isolated vertex must be a center, as otherwise the cost of the solution would be infinite. Thus, whenever a vertex is sampled to enter a supporting candidate set, or whenever a vertex leaves or enters an approximate ball or a leaking set, we charge the vertex to one of its incident edges.↩︎

26. This \(i\)-th level existed before the adversarial edge insertion, because the radius of a new level must decrease the first time it appears (see also the comment at Line [algline:comment95nu95largest] in 4).↩︎

27. Note that these definitions are similar to Definition 5 and Definition 6.↩︎

28. Note that 21 inherits the high probability bound from 4.↩︎

29. For unweighted graphs, the stretch of the spanner is \(2\lambda-1\); the \(O(2\lambda-1)\) arises for weighted graphs.↩︎

30. The two algorithms by Mettu and Plaxton in [28] and [29] (which includes the MP-bi algorithm) are different.↩︎

31. Since the algorithm never removes vertices from \(S\), we actually have \(S = \sigma_\text{max}(V)\).↩︎

32. The dynamic spanner algorithm \(\mathcal{SP}\) processes each distance decrease in the batch \(B\) separately.↩︎

33. Recall that based on the discussion in 8, we can safely assume that the static \((k, z)\)-clustering algorithm of 24 works on weighted \((k, z)\)-clustering instances.↩︎

34. Using the convention that the minimum of an empty set is \(\infty\).↩︎

35. During the first stage in which we use our incremental bicriteria approximation 4, the maintained solution is of size \(\tilde{O}(k)\). Thus whenever \(m < k\), an alternative approach is to extend the solution by adding the endpoints of each inserted edge; once \(m \geq k\), the algorithm begins.↩︎

36. During the second stage in which we use our incremental reduction 5, the amortized update time is \(\tilde{O}(k^{1+\epsilon})\) for some \(\epsilon \in (0, 1)\).↩︎

37. We emphasize that in 6, the corresponding set \(X_i\) must be a subset of \(V\) and not just of \(U_i\).↩︎