Online Balanced Allocation of Dynamic Components

We adopt the competitive analysis framework to analyze OBADC algorithms. A deterministic (resp. randomized) online algorithm $𝒜$ is said to be $\rho$-competitive (alternatively, $\rho$ is the competitive ratio of $𝒜$) if for any input sequence $\sigma$, the cost (resp. expected cost) $c(𝒜,\sigma )$ incurred by $𝒜$ in $\sigma$ satisfies $c(𝒜,\sigma )\le \rho \text{OPT}(\sigma )+\gamma$ where $\gamma$ is a constant independent of the length of $\sigma$ and OPT$(\sigma )$ is the cost of an optimal offline algorithm denoted by OPT, which has complete information about the request sequence $\sigma$ in advance. Abusing notation slightly, we refer to OPT$(\sigma )$ as OPT when $\sigma$ is clear from context.

To capture the practical objective of utilizing a number of clusters proportional to the total resource requirement (which varies over time), we seek algorithms which are also competitive with respect to the number of clusters utilized by OPT. Let $n_t$ denote the number of vertices at any time $t$, and let ${\alpha }_t,{\beta }_t$ denote the number of clusters used to assign all $n_t$ vertices at time $t$ by OPT and an online algorithm $𝒜$. We say that $𝒜$ is $\mu$-resource competitive if for all time $t$, ${\beta }_t\le \mu {\alpha }_t$.

For the sake of obtaining polynomial-time online algorithms, we consider an overprovisioned setting, similar to the one considered in a recent work [23]. Here, each cluster $C_i$ for $i\in [\mathrm{\ell }]$ has capacity $(1+\epsilon )k$ for some $\epsilon \in (0,1)$. While seemingly similar to a $(1+\epsilon )$ resource-augmented model, we emphasize that in the over-provisioned setup, both the online algorithm and the optimal offline algorithm OPT are constrained to an identical cluster capacity of $(1+\epsilon )k$ for any cluster $C_i$. As a result, competitiveness is analyzed on a stricter benchmark, in that the optimal offline and online algorithm have access to the same amount of resources, in strong contrast to resource augmentation where competitiveness is analyzed with respect to an unaugmented offline algorithm (see Chapter 4 of [25]).

Our main result is a $O(\log k)$-competitive algorithm for OBADC in the over-provisioned setting. We show that the competitive ratio of our algorithm is asymptotically optimal by establishing a lower bound. Furthermore, our algorithm is $(2+\epsilon )$-resource competitive.

In a resource augmented setting where the optimal offline algorithm is constrained to capacity $k$ per cluster, our algorithm obtains $O(\log k)$ competitiveness, while utilizing a number of clusters within $(1+\epsilon )$ factor of the minimum. The proof of resource-competitiveness is deferred to the full version of the paper.

We next investigate OBADC in the context of “algorithms with predictions” which is a growing research area [25, 15] with the over-arching goal of circumventing pessimistic limitations of lower and upper bounds for various problems in online, dynamic and approximation algorithms.
Prediction Model: At any time step $t$ when a vertex $v$ is inserted, with probability $\eta \ge 0$, we also receive a set $P_v$ consisting of all vertices in $V_t$ that lie in the same component as $v$, where $V_t$ denotes the set of vertices at the beginning of time step $t$. Note that with probability $1-\eta$, we do not receive any information on the component of $v$. Furthermore, $P_v$ only consists of vertices in $v$’s component which exist at time $t$, and contains no information about future vertices in $v$’s component which may arrive after time $t$.

Our “prediction error” is quantified by the confidence $\eta >0$ of the predictions, similar to [11] and we analyze the performance of a learning-augmented online algorithm for OBADC in a standard consistency-robustness framework [11, 15, 24]. An algorithm $𝒜$ for OBADC with predictions is said to be $\alpha$-consistent and $\beta$-robust if it is $\alpha$-competitive when $\eta =1$, and $\beta$-competitive where $\beta$ is a non-increasing function of $\eta$. Roughly speaking if $\eta =1$, and we have perfect predictions, then one would desire constant-factor competitiveness. On the other hand, as $\eta$ approaches 0, the performance of the algorithm should gracefully degrade to the competitive ratio obtained by the best-known online algorithm for the problem. Our second result provides a near-tight consistency-robustness tradeoff for OBADC.

At a high-level, OBADC is related to previous work on online partitioning of dynamically changing graphs. Related problems include variants of online graph coloring and the OBGR problem. In recent work, Azar et al. [3] introduce an online graph recoloring problem in which edges of a graph arrive online and an algorithm needs to distribute the vertices among $\mathrm{\ell }$ clusters such that for any edge, the two endpoints must be in different clusters. Subsequent work [23] considers a capacitated variant of online recoloring. A key distinction between such coloring problems and OBADC is that while an edge in the former requires the endpoints to be separated, an edge in the latter requires the endpoints to be co-located, leading to different technical considerations.

OBADC is perhaps most closely related to OBGR [2], in which there is a static set $V$ of $n=kl$ vertices and a set of $l>0$ clusters each holding $k$ vertices initially. An online sequence $\sigma ={\{(u_t,v_t)\}}_{t>0}$ of communication requests arrives over time. The cost of serving request $(u_t,v_t)$ is 1 if $u_t$ and $v_t$ are in distinct clusters and $0$ otherwise. Prior to serving any request, a vertex can be migrated at a cost of $\alpha \in {\mathbb{Z}}^{>0}$. The cost incurred by an online algorithm is the total communication and migration cost to serve all requests in $\sigma$. OBGR has a $O(k^2{l}^2)$-competitive algorithm [2] in the non-augmented setting while a lower bound of $\mathrm{\Omega }(kl)$ is known. In recent work, a $O(kl{2}^{O(k)})$-competitive algorithm was given in [4], which is optimal for constant $k$. In the resource augmented setting, with $(2+\epsilon )$-augmented cluster capacity an $O(k\log k)$-competitive deterministic algorithm was given in [2]. For the same setting, a polynomial time algorithm was recently presented in [10]. A lower bound of $\mathrm{\Omega }(l)$ holds even in the $(1+\epsilon )$-augmented setting where  [20].

In [14], Henzinger et al. introduced the learning model of the problem in which the vertex set of the graph $G_{\sigma }$ induced by the request sequence $\sigma$ can be partitioned into $V_1,\mathrm{\dots }.V_l$ such that $|V_i|=k$ for all $i$ and there are no inter-cluster requests $(u,v)$ where $u\in V_i.v\in V_j$ for $j\ne i$. For the learning model, the lower bound of $\mathrm{\Omega }(kl)$ holds in the non-augmented setting. Allowing $(1+\epsilon )$-augmentation, the best deterministic and randomized algorithms are $\mathrm{\Theta }(l\log k)$ and $\mathrm{\Theta }(\log k+\log l)$-competitive respectively which are shown to be tight[13].

We describe the similarities and differences between OBADC and OBGR. OBADC resembles a “fully dynamic” version of OBGR in the learning model, but differs as follows. In OBADC, vertices arrive and depart over time, and hence the online algorithm has to adapt to communication patterns which evolve over time between both existing vertices and new vertices. The migration costs are identical between the two models; however in OBADC, an insertion of a new vertex incurs a cost of $1$ and we aim to have the total number of clusters utilized by an online algorithm to adapt with the number of vertices. This may incur strategic migrations of vertices to satisfy this additional objective, in contrast to OBGR where migrations are performed to solely minimize communication overhead.

To circumvent pessimistic lower-bounds and obtain polyonomial time algorithms, many online algorithmic problems have been studied in the resource-augmented model (e.g., see [21, 33, 34]), going back as far as the earliest work on caching [29]. OBGR has also been studied in the resource-augmentation model [13, 22, 10, 2], where OPT is constrained to a capacity of $k$ on each cluster, while an online algorithm can utilize capacity $(1+\epsilon )k$ for some $\epsilon >0$. In contrast, we study OBADC in an over-provisioned setting, which yields stronger guarantees than resource-augmentation since the algorithm and the optimal have the same resources. Any competitive ratio in the over-provisioned model immediately implies the same bound in the resource augmented model; for the measure of number of clusters utilized, we are able to get stronger bounds in the resource-augmentation model (see the remark after Theorem 1 in Section 1.1).

Another approach toward addressing pessimistic bounds in online and approximation algorithms is to incorporate the growing availability of machine-learned predictions in the design of algorithms [11, 18, 15, 5]. A central theme in this area is the following: given access to an imperfect machine-learned oracle which can “predict” characteristics of future request sequences or actions (in the context of online algorithms [24, 15]), edge updates (in the context of dynamic algorithms [5]) or optimal solutions (in the context of approximation algorithms [8]), can improved competitive ratios, running/update times, or approximation ratios be obtained? The imperfection of predictions is quantified by prediction error, which is problem and instance dependent, or a confidence parameter [11]. There is a great variation in terms of various prediction models and prediction errors which have been utilized and there is no singular notion of either, which can be useful or applicable to wide variety of problems.

Our study of online OBADC with predictions is also inspired from prior empirical work in VM allocation and migration, in which various predictions on resource utilization in clusters [17], future VM requests and migrations [19], and communication traffic from historically collected data have been utilized towards efficient provisioning of resources.

Our algorithm classifies components according to their size. For a component $C\in 𝒞$, we say that $C$ is in class $i$ if $|C|\in [{(1+\frac{\epsilon }{4})}^{i-1},{(1+\frac{\epsilon }{4})}^i)$, where $1\le i\le \lfloor {\ln }_{(1+\frac{\epsilon }{4})}k\rfloor$. We say that a component is small if it is in class $i$ where $i\le c_s$ where $c_s\le \lfloor {\ln }_{(1+\frac{\epsilon }{4})}\frac{\epsilon k}{4}\rfloor$. Thus, any small component has size at most $Dk$ where $\frac{\epsilon }{5}\le D\le \frac{\epsilon }{4}$. All the other components are said to be large.

A large component is understood to be in class $i$ if it is in class $i+c_s$. By the above definitions, it follows that a large component of class $i$ has size in $[Dk{(1+\frac{\epsilon }{4})}^{i-1},Dk{(1+\frac{\epsilon }{4})}^i)$. The following lemma bounds the number of large component classes.

Note that a large component has volume at least $\frac{\epsilon k}{5}$ and at most $k$. Thus, $c_l\le \frac{\ln (\frac{5}{\epsilon })}{\ln (1+\frac{\epsilon }{4})}+1$. Since $1-\frac{1}{x}\le \ln x\le x-1$ for any $x\in {ℝ}^{\ge 0}$, it follows that $c_l\le \frac{(5/\epsilon )}{1/(1+\epsilon /4)}\le \frac{4+\epsilon }{\epsilon }\cdot \frac{5}{\epsilon }+1\le \frac{26}{{\epsilon }^2}$ since . $◀$

For every component $C\in 𝒞$, our algorithm provisions volume on some cluster $S_i\in 𝒮$ to which it is assigned, which we refer to as the assigned volume and denote it by $A(C)$.

For any cluster $S_i\in 𝒮$ let $A(S_i)$ denote the total assigned volume for all components assigned to $S_i$. Let $R_i$ denote the residual unassigned volume of $S_i$, where $R_i=(1+\epsilon )k-A(S_i)$. We present a fine-grained scheme to assign volumes to components as follows.

Let $A_{ij}=(1+j\frac{\epsilon }{16}){(1+\frac{\epsilon }{4})}^{i-1}$, for $j\in \{0,1,2,3,4\}$. Thus, $A_{i0}={(1+\frac{\epsilon }{4})}^{i-1}$ and $A_{i4}={(1+\frac{\epsilon }{4})}^i$. Our algorithm maintains the following invariant for assigned volumes at all times.

The following lemma is immediate based on the invariant above.

A cluster is said to be active if there is at least one component assigned to it. The set of all active clusters is denoted by ${𝒮}_A$.

Our algorithm marks and un-marks active clusters over time. If a cluster is marked, then its residual volume is small. We denote the set of marked clusters by ${𝒮}_M$, where ${𝒮}_M\subseteq {𝒮}_A$. Initially, all clusters are unmarked, i.e. ${𝒮}_M=\mathrm{\varnothing }$. Our algorithm maintains the following invariant at all times.

Furthermore, let ${𝒮}_S$ denote the set of clusters on which only small components (and no large components) are assigned and let ${𝒮}_L$ denote the set of clusters to which at least one large component is assigned. To ensure that the number of active clusters is at most $(2+\epsilon )$ times the minimum needed, our algorithm maintains the following invariant.

Our algorithm marks and un-marks certain components when their component class decreases due to vertex deletions. If a large component of class $i\in [c_l-1]$, (resp. a small component of class $c_s$) is marked, then it is treated as a large component of class $i+1$ (resp. a large component of class 1). Intuitively, we mark a component to ensure that the ILP is not solved too frequently if its volume shrinks only slightly due to deletions. The set of marked components at any time is denoted by ${𝒞}_M$. Note that all marked components are treated as large components by our algorithm, thus ${𝒞}_M\subseteq {𝒞}_L$. Our algorithm maintains the following invariant for marked components.

Our algorithms maintain the sets ${𝒞}_S$ and ${𝒞}_L$ of small and large components, respectively, together with the set ${𝒞}_M$ of marked components. For a component $C$, the assigned volume $A(C)$ is maintained, and for all $S_i\in 𝒮$, $A(S_i)$ and $R_i$ are maintained. Furthermore, the sets of clusters ${𝒮}_A,{𝒮}_M,{𝒮}_S$ and ${𝒮}_L$ are maintained.

In the following section, we outline our approach for assigning large components which is completely independent of the assignment of small components.

We first note that $Dk{(1+\frac{\epsilon }{4})}^{i-1}-\frac{{\epsilon }^{2}k}{100}\ge Dk-\frac{{\epsilon }^{2}k}{100}\ge \frac{\epsilon k}{5}-\frac{{\epsilon }^{2}k}{100}\ge \frac{\epsilon k}{6}$ for any $i>0$. Thus, any entry ${\tau }_i$ is upper bounded by $\frac{k}{\epsilon k/6}=\frac{6}{\epsilon }$. Since the number of large component classes is $\frac{26}{{\epsilon }^2}$ by Lemma 3, the total number of signatures is at most ${(\frac{6}{\epsilon })}^{\frac{26}{{\epsilon }^2}}=O(1)$. $◀$

We solve an integer linear program (ILP) in polynomial time, and obtain signatures which guide the placement of large components. Let $T_{ij}$ denote the $j^{th}$ entry of a signature $T_i\in 𝒯$. For each signature $T_i$, we let $x_i\in [0,\mathrm{\ell }]$ denote the number of clusters which are assigned signature $T_i$. Let ${\sigma }_j$ denote the number of class $j$ large components at any given point in time. Our ILP is as follows.

In matrix form, our ILP has $n_r=O(c_l)=O(1)$ rows and $n_c=O(|𝒯|)=O(1)$ columns. Thus, the ILP can be solved in polynomial time.

Our algorithm solves this ILP whenever ${\sigma }_j$ changes for any $j\in [c_l]$. This could be after components are merged leading to a larger component with a higher component class or, vertex deletions from a component leading to a decrease in its component class. In both cases, at most three components in $𝒞$ change, and as a result, at most three component classes change. We invoke a well-known result in sensitivity analysis from [27], which quantifies the change in optimal solutions of the ILP.

We prove the following lemma.

Whenever two components are merged or a deletion causes a large component’s size class to decrease, the RHS vector in our ILP changes by at most $1$ in the infinity norm. To bound the sub-determinant, we use the Hadamard inequality to derive that $\mathrm{\Delta }\le {(n_c{A}_{\max })}^{n_c/2}$ where $A_{\max }$ denotes the maximum entry (in absolute value) of the constraint matrix $A$. Each entry in the constraint matrix of our ILP has value either 1 or $T_{ij}$ so that $A_{\max }\le \frac{k}{Dk}=O(\frac{1}{\epsilon })$. As a result, $\mathrm{\Delta }=O({(\frac{|𝒯|}{\epsilon })}^{|𝒯|})$. Thus, the optimal solution to the ILP changes by $O(|𝒯|\mathrm{\Delta })$ in the infinity norm. Since $x$ has dimension $|𝒯|$, the number of signatures which change between any two optimal solutions is $O({|𝒯|}^2\mathrm{\Delta })=O(1)$. $◀$

Given the solution $x=(x_1,x_2,\mathrm{\dots },x_{|𝒯|})$ from the ILP, we perform a greedy assignment of signatures to clusters which minimizes the number of clusters whose assigned signatures change. Let $x^{\prime }=(x_1^{\prime },x_2^{\prime },\mathrm{\dots },x_{|𝒯|}^{\prime })$ denote the current signature, such that there are exactly $x_i^{\prime }$ clusters which are assigned signature $T_i$. Our algorithm for greedy assignment, Assign-Signatures works as follows.

Let $z_i=x_i$ for all $i\in [|𝒯|]$ and ${𝒮}^{\prime }≔{𝒮}_A$ denote the set of active clusters. We iterate over all $i\in [|𝒯|]$: while $z_i>0$, if there exists an active cluster $S_j$ in ${𝒮}^{\prime }$ which is currently assigned signature $T_i$, $z_i$ is decremented, $S_j$ is removed from ${𝒮}^{\prime }$ and we continue. Else if no cluster in ${𝒮}^{\prime }$ is assigned signature $T_i$, we pick an arbitrary active cluster $S_j$ in ${𝒮}_A$ and assigns $T_i$ to $S$. If ${𝒮}^{\prime }=\mathrm{\varnothing }$, our algorithm picks an arbitrary inactive cluster $S_j\in 𝒮\backslash {𝒮}_A$, adds $S_j$ to ${𝒮}_A$ and assigns $T_i$ to $S$.

Let ${𝒮}_N\subseteq {𝒮}_A$ denote the set of clusters which are assigned a new signature after the call to Assign-Signatures. Any cluster $S\in {𝒮}_N$ satisfies one of the following conditions prior to the call to Assign-Signatures: i) $S$ was inactive, ii) $S$ was active but its signature changed after the call to Assign-Signatures or iii) $S$ was active and was not assigned any signature prior to the call to Assign-Signatures.

Let ${𝒮}_O\subseteq 𝒮$ denote the set of clusters which were assigned a signature prior to solving the ILP, and are no longer assigned a signature. Finally, let ${𝒮}_I$ denote the set of clusters whose assigned signatures are identical before and after the call to Assign-Signatures. Our algorithm returns sets ${𝒮}_N,{𝒮}_O$ and ${𝒮}_I$. Clearly, the assigned signatures change only for clusters which are in ${𝒮}_N\cup {𝒮}_O$.

By virtue of subroutine Assign-Signatures and Lemma 8, the following lemma is immediate.

For all clusters $S_i\in {𝒮}_I$ whose assigned signatures do not change, our algorithm does not modify the assignment of large components. Let ${𝒞}_L^{\prime }$ denote the set of all large components in ${𝒞}_L$ which are not assigned to any cluster in ${𝒮}_I$. It follows from Lemma 9 that the total volume of all large components in ${𝒞}_L^{\prime }$ is $O(kf(\epsilon ))$.

Components in ${𝒞}_L^{\prime }$ are assigned to clusters in ${𝒮}_N$, corresponding to the newly assigned signatures. Let ${𝒞}_S^{\prime }$ denote the set of all small components previously assigned to ${𝒮}_N\cup {𝒮}_O$. From Lemma 9, it follows that the total volume of all components in ${𝒞}_S^{\prime }$ is $O(kf(\epsilon ))$. Our algorithm re-assigns small components in ${𝒞}_S^{\prime }$ in a first-fit fashion, explained in the next section. The following Lemma is immediate from Lemma 8, Lemma 9 and our preceding discussion.

This subroutine takes as input a component $C$, and a cluster $S_j\in {𝒮}_A$ and assigns volume for $C$ on $S_j$. In the case when $C$ is a class $i-1$ marked component, it is treated as a class $i$ component and assigned volume $A_{i2}$.

Observe that Invariant 1 is satisfied for any component $C$ after a call to Assign-Volume.

The subroutine Assign-Small is invoked whenever a small component $C$ needs to be assigned volume on a cluster. We iterate over active unmarked clusters $S_j\in {𝒮}_A\backslash {𝒮}_M$, and if $R_j\ge (1+\frac{\epsilon }{4})|C|$, $C$ is assigned to $S_j$. Else, $S_j$ is marked and added to ${𝒮}_M$.

If all clusters are marked, i.e. ${𝒮}_M={𝒮}_A$ we add an arbitrary cluster in $𝒮\backslash {𝒮}_A$ to ${𝒮}_A$ and assign volume for $C$.

The subroutine Handle-Insertion is called whenever a request $r_t$ at time $t$ corresponds to a vertex insertion $v$. Subroutine Assign-Small is invoked to assign the singleton component $\{v\}$.

This subroutine takes as input a component $C$ which is currently assigned to a cluster $S_i$. The quantity $A(S_i)$ is decremented by $A(C)$ and $A(C)$ is set to $0$. If $S_i\in {𝒮}_M$ and $R_i\ge \frac{\epsilon k}{3}$, $S_i$ is unmarked. The reason why $S_i$ is unmarked is that if $R_i\ge \frac{\epsilon k}{2}$, a small component can be assigned volume on $S_i$, since the assigned volume for a small component is bounded by by Invariant 1. The pseudo-code is given as follows.

This subroutine takes as input a newly unmarked cluster $S_i$. If the assigned volume $A(S_i)=0$, then $S_i$ is removed from the sets ${𝒮}_A$ and ${𝒮}_S$. If $|{𝒮}_S|>0$, an arbitrary cluster $S\in {𝒮}_S$ is chosen and unmarked.

Else, if $A(S_i)>0$, Invariant 3 is restored as follows. Note that if $S_i\in {𝒮}_L$ and ${𝒮}_S=\mathrm{\varnothing }$ or $S_i\in {𝒮}_S$ and $|{𝒮}_S|=1$, nothing needs to be done since Invariant 3 is already maintained. Else, let $S\in {𝒮}_S$ denote an unmarked cluster where $S\ne S_i$. While the residual volume of $S_i$ is sufficient (and $S_i$ is unmarked and $|{𝒮}_S|>0$) small components from $S$ are migrated to $S_i$. If the residual volume of $S_i$ is insufficient, $S_i$ is marked and added to ${𝒮}_M$. If at any point $A(S)=0$, $S$ is removed from ${𝒮}_A$ and ${𝒮}_S$. Thereafter, if $S_i\in {𝒮}_L$, and $|{𝒮}_S|>0$, an arbitrary cluster $S$ in ${𝒮}_S$ is unmarked. If $S_i\in {𝒮}_S$, and $|{𝒮}_S|>1$, an arbitrary cluster in ${𝒮}_S$ is unmarked. The procedure continues while the residual volume of $S_i$ is sufficient. On the other hand, if $S_i$ is the only cluster in ${𝒮}_S$ it is unmarked and the process terminates.

We give a subroutine Reassign-Large which is invoked whenever the number of large components ${\sigma }_i$ of any class $i\in [c_l]$ change. In Reassign-Large, the subroutine Assign-Signatures is invoked which returns the sets ${𝒮}_N,{𝒮}_O$ and ${𝒮}_I$ of clusters (see Section 2.2).

Let ${𝒞}_S^{\prime }$ denote the set of all small components assigned to clusters in ${𝒮}_O\cup {𝒮}_N$. Small components currently assigned to clusters in ${𝒮}_O\cup {𝒮}_N$ are unassigned. Clusters in ${𝒮}_O\cup {𝒮}_N$ are unmarked and the set of active clusters ${𝒮}_A$ is updated by removing clusters in ${𝒮}_O$ and adding clusters in ${𝒮}_N$.

Next, let ${𝒞}_L^{\prime }$ denote the set of large components which are not assigned to any cluster in ${𝒞}_I$. For all clusters $S\in {𝒮}_N$, let $T_s$ be the signature assigned to cluster $S$. For all non-zero $T_{sa}$ where $a\in [c_l]$, a class $a$ large component $C$ is chosen from ${𝒞}_L^{\prime }$, and $\text{Assign-Volume}(S,C)$ is invoked, concluding the the assignment of large components.

For small components $C\in {𝒞}_S^{\prime }$, Assign-Small$(C)$ is invoked. Finally, for all unmarked clusters $S$ in ${𝒮}_N\notin {𝒮}_M$, Handle-Unmarked$(S)$ is invoked. The pseudo code of Reassign-Large is deferred to the full version of the paper.

We present a subroutine Handle-Deletion which takes as input a vertex $v$ to be deleted. We assume that Invariant 1 holds prior to the deletion request. Let $C$ denote the component containing $v$ prior to $v$’s deletion s.t. $|C|\in [{(1+\frac{\epsilon }{4})}^{i-1},{(1+\frac{\epsilon }{4})}^i)$ and $S_j$ denote the cluster to which $C$ is assigned. We consider two cases.

1. 1.

   $C$ is small and unmarked: Vertex $v$ is removed from $C$. There are five sub-cases to consider.

   1. (a)

      If $A(C)=A_{i+1,2}$ and , then $A(C)$ is set to $A_{i+1,1}$.

   2. (b)

      If $A(C)=A_{i+1,1}$ and , then $A(C)$ is set to $A_{i4}$.

   3. (c)

      If $A(C)=A_{i4}$ and , then $A(C)$ is set to $A_{i3}$.

   4. (d)

      If $A(C)=A_{i3}$ and , then $C$ has become a class $i-1$ component. $A(C)$ is set to $A_{i2}$.

   5. (e)

      If $C=\mathrm{\varnothing }$, $A(C)$ is set to $0$.

   In all of the above cases, $A(S_j)$ and $R_j$ are updated. If $S_j\in {𝒮}_M$ and $R_j\ge \frac{\epsilon k}{2}$, $S_j$ is removed from ${𝒮}_M$ and Handle-Unmarked$(S_j)$ is invoked.

2. 2.

   $C$ is large or marked: We first remove $v$ from $C$. We consider the following cases.

   1. (a)

      $C$ is large and unmarked (i.e. $C\in {𝒞}_L\backslash {𝒞}_M$): Our algorithm considers the following cases.

      1. i.

         If $A(C)=A_{i+1,2}$ and , then $A(C)$ is set to $A_{i+1,1}$.

      2. ii.

         If $A(C)=A_{i+1,1}$ and , then $A(C)$ is set to $A_{i4}$.

      3. iii.

         If $A(C)=A_{i4}$ and , then $A(C)$ is set to $A_{i3}$.

      4. iv.

         If , $C$ is marked. If $A(C)=A_{i3}$ then $A(C)$ is set to $A_{i2}$.

      In the above cases, if $S_j\in {𝒮}_M$ and $R_j\ge \frac{\epsilon k}{2}$, $S_j$ is removed from ${𝒮}_M$ and Handle-Unmarked$(S_j)$ is invoked.

   2. (b)

      $C$ is marked: There are two cases to consider depending on whether $C$ is large or small (after the deletion of $v$).

      1. i.

         Let $C$ be a marked large component of class $c$ where $c=i-c_s$, such that $c\in [c_l-1]$. If $|C|\ge Dk{(1+\frac{\epsilon }{4})}^c-\frac{{\epsilon }^{2}k}{100}$, there is nothing to be done. Else, if , $C$ is unmarked. The counter ${\sigma }_{c+1}$ is decremented since $C$ is now considered a class $c$ component, and ${\sigma }_c$ is incremented. Then, the subroutine Reassign-Large is invoked.

      2. ii.

         Let $C$ be a marked small component of class $c_s$. If $|C|\ge Dk-\frac{{\epsilon }^{2}k}{100}$, nothing is done. Else, if , $C$ is first unmarked. Then, $C$ is removed from ${𝒞}_L$ and added to ${𝒞}_S$. The counter ${\sigma }_1$ is decremented. Then, the subroutine Reassign-Large is invoked.

The pseudo-code of Handle-Deletion is deferred to the full version of the paper.

The subroutine Merge-Components is invoked by our algorithm to handle a merge request $(u,v)$. Let $C_i$, $C_j$ denote the components of $u$ and $v$ respectively. If $C_i=C_j$, nothing needs to be done. Otherwise, w.l.o.g., let $|C_j|\le |C_i|$ and $S_i$ and $S_j$ denote the clusters on which $C_i$ and $C_j$ are currently assigned. Let $C_m=C_i\cup C_j$.

1. 1.

   $C_m$ is small: The subroutine Handle-Small is called and considers two cases.

   1. (a)

      $C_i$ is marked: We note that $C_j$ cannot be a marked component since this would contradict that $C_m$ is small. This is because if $C_j$ is marked, then $|C_m|\ge 2(Dk-\frac{{\epsilon }^{2}k}{100})=Dk+Dk-\frac{{\epsilon }^{2}k}{50}>Dk$ since $Dk-\frac{{\epsilon }^{2}k}{50}>\frac{\epsilon k}{5}-\frac{\epsilon k}{50}>0$. Thus, the only possibility is that $C_i$ is marked. Since any marked small component must have volume at least $Dk-\frac{{\epsilon }^{2}k}{100}$, and $C_m$ is small it follows that $|C_m|\le Dk$. In this case we note that $A(C_i)=A_{i2}\ge Dk$ so that $A(C_m)$ can be set to $A(C_i)$. $C_i$ is removed from ${𝒞}_M$ and $C_m$ is added to ${𝒞}_M$. If , $C_m$ is added to ${𝒞}_M$. As such, $C_m$ is still treated by our algorithm as a large marked component. If $S_i=S_j$ nothing needs to be done. Else, vertices in $C_j$ are migrated to $S_i$, and Unassign-Volume($C_j,S_j)$ is invoked. Subroutine $\text{Handle-Unmarked}(S_j)$ is invoked to handle the case when $S_j$ becomes unmarked.

   2. (b)

      $C_i$ and $C_j$ are not marked: In this case, there are two cases to consider.

      1. i.

         If $A(C_i)\ge |C_m|$, we set $A(C_m)$ to $A(C_i)$ and $A(C_i),A(C_j)$ to $0$. If $S_j=S_i$, nothing needs to be done. If $S_j\ne S_i$, vertices in $C_j$ are migrated to $S_i$, and $\text{Unassign-Volume}(C_j)$ is invoked. Subroutine Handle-Unmarked$(S_j)$ is invoked to handle the case if $S_j$ becomes unmarked.

      2. ii.

         If , we invoke $\text{Unassign-Volume}(C_i,S_i)$ and $\text{Unassign-Volume}(C_j,S_j)$. If $R_i\ge (1+\frac{\epsilon }{4})|C_m|$, we call $\text{Assign-Volume}(C_m,S_i)$. If $S_i\ne S_j$, we migrate vertices in $C_j$ to $S_i$. We invoke Handle-Unmarked$(S_j)$ and Handle-Unmarked$(S_i)$.

         On the other hand, if , $S_i$ is marked and $\text{Assign-Small}(C_m)$ is invoked.

2. 2.

   $C_m$ is large: The subroutine Handle-Large is invoked which adds $C_m$ to the set of large components.

   Let $m^{\prime }\in [c_l]$ be an integer such that $|C_m|\in [Dk{(1+\frac{\epsilon }{4})}^{m^{\prime }-1},Dk{(1+\frac{\epsilon }{4})}^{m^{\prime }})$. If $C_i$ is marked, i.e. $C_i\in {𝒞}_M$, let $i^{\prime }≔a+1$ be the integer where $a$ is an integer such that $|C_i|\in [Dk{(1+\frac{\epsilon }{4})}^a-\frac{{\epsilon }^{2}k}{100},Dk{(1+\frac{\epsilon }{4})}^a)$, else we let $i^{\prime }≔a$ be the integer where $a$ is an integer such that $|C_i|\in [Dk{(1+\frac{\epsilon }{4})}^{a-1},Dk{(1+\frac{\epsilon }{4})}^a)$. We consider the following cases.

   1. (a)

      $C_j$ is large or $C_j$ is marked or $m^{\prime }>i^{\prime }$: If $C_j$ is marked, we let $j^{\prime }≔a+1$ be the integer where $a$ is an integer such that $|C_j|\in [Dk{(1+\frac{\epsilon }{4})}^a-\frac{{\epsilon }^{2}k}{100},Dk{(1+\frac{\epsilon }{4})}^a)$. Else if $C_j$ is unmarked, we let $j^{\prime }≔a$ be the integer where $a$ is an integer such that $|C_j|\in [Dk{(1+\frac{\epsilon }{4})}^{a-1},Dk{(1+\frac{\epsilon }{4})}^a)$. We decrement ${\sigma }_{j^{\prime }}$ and ${\sigma }_{i^{\prime }}$ by 1, and increment ${\sigma }_{m^{\prime }}$ by 1. We remove $C_i,C_j$ from ${𝒞}_M$ to make sure that the set of marked components is updated. Thereafter, we update the component sets ${𝒞}_S,{𝒞}_L$ and call subroutine Reassign-Large to handle the assignment of large components.

   2. (b)

      $C_j$ is small and $C_j$ is unmarked and $m^{\prime }\le i^{\prime }$: In this case, we note that ${\sigma }_{i^{\prime }},{\sigma }_{m^{\prime }}$ do not change. Thus, the ILP is not solved. We assign volume for the merged component as follows.

      In the case when $A(C_i)\ge A(C_m)$, vertices in $C_j$ are migrated to $S_i$ if $S_i\ne S_j$. We invoke Unassign-Volume$(C_j,S_j)$, and $\text{Handle-Unmarked}(S_j)$. Else, nothing needs to be done. The assigned volumes $A(C_i),A(C_j)$ are set to $0$. If $C_i$ is marked and , then $C_i$ is removed from ${𝒞}_M$ and $C_m$ is added to ${𝒞}_M$. We note that in this case, $A(C_i)=A_{i^{\prime }2}\ge A(C_m)$.

      If , then we invoke Unassign-Volume$(C_i,S_i)$ and $\text{Unassign-Volume}(C_j,S_j)$.

      If $R_i\ge (1+\frac{\epsilon }{4})|C_m|$, we assign volume for $C_m$ on $S_i$ by invoking $\text{Assign-Volume}(C_m,S_i)$. If $A(S_j)=0$, we call Handle-Unmarked$(S_j)$. Next, we call $\text{Handle-Unmarked}(S_i)$. In the case when $A(S_j)\ne 0$ (and $S_j\in {𝒮}_A$ as a result), we invoke $\text{Handle-Unmarked}(S_j)$.

      If , we do the following. While , we call Unassign-Volume$(C,S_i)$ where $C$ is an arbitrary small component assigned on $S_i$, and add it to a set ${𝒞}_S^{\prime }$. Once $R_i\ge (1+\frac{\epsilon }{4})|C_m|$, we invoke $\text{Assign-Volume}(C_m,S_i)$ and migrate vertices in $C_j$ to $S_i$ if needed (in the case when $S_i\ne S_j$) together with a call to Unassign-Volume$(C_j,S_j)$. Next, we assign components in ${𝒞}_S^{\prime }$ to $S_i$ as long as there is sufficient volume and $S_i$ is not marked. If all components in ${𝒞}_S^{\prime }$ have been assigned and $S_i$ is unmarked, we call Handle-Unmarked$(S_i)$.

      If $S_j$ is unmarked, we invoke $\text{Handle-Unmarked}(S_j)$. All remaining unassigned components $C$ in ${𝒞}_S^{\prime }$ (if any) are assigned by invoking $\text{Assign-Small}(C)$. Finally, the component sets ${𝒞}_S,{𝒞}_L$ are updated.