Online Steiner Forest with Recourse

Imase and Waxman’s $O(\sqrt{n})$-recourse result for Steiner tree [59] in fact also holds in a more general setting where the input sequence consists of terminal insertions as well as deletions. For this setting, Łącki, Oćwieja, Pilipczuk, Sankowski, and Zych [65] gave a constant-competitive algorithm with $O(\log \mathrm{\Delta })$ recourse, where $\mathrm{\Delta }$ is the ratio of the maximum to minimum distance in the metric. Gupta and Kumar [54] improved this to $O(1)$ recourse. Gupta and Levin [57] recovered the result of [65] in a more general setting of submodular cover. In all of these results, the recourse bounds are amortized.

On a high level, a clustering procedure will maintain a clustering $𝒞$ (i.e., a partition) of the terminals and iteratively merge two active clusters in $𝒞$ which are close enough in the contracted metric $ℳ/𝒞$ (we can think of the input metric $ℳ$ as a complete weighted graph on the terminals²²2In our model, we assume that the input metric $ℳ$ has no Steiner node, i.e., $ℳ$ is a metric on terminals. See Section 2 and particularly Remark 3 for a further discussion. and of $ℳ/𝒞$ as the graph with each cluster contracted into a single vertex). In the clustering procedure for Steiner tree, clusters are always active, which means that the procedure is equivalent to merging clusters which are close in the original metric $ℳ$, and therefore, adding one edge to the solution suffices to simulate this merge. In contrast, in the clustering procedure for Steiner forest, some clusters will become inactive (i.e., they will stay in the clustering without participating in further merge operations). Hence, we need to measure the closeness in the contracted metric $ℳ/𝒞$, and thus simulating a merge operation between clusters $C_1,C_2\in 𝒞$ requires us to add into the solution a $C_1$-$C_2$ shortest path in $ℳ/𝒞$, which potentially consists of many edges.

We note that the difference between the clustering procedures for these two problems is rooted in the inherent difference between Steiner forest and Steiner tree: a Steiner tree solution must be connected, while a Steiner forest solution may not. This is also the fundamental barrier to overcome when designing Steiner forest algorithms in other settings (e.g., the offline and classic online settings).

In other words, while applying the approach in [50] to Steiner forest may control recourse with respect to merges and their revocations (that is, when comparing the clustering procedures for two consecutive arrivals $t-1$ and $t$, some merges done at $t-1$ may be revoked, and new merges may be performed at $t$), it remains unclear how to bound the recourse in terms of edge changes.

We proceed completely differently from [50] and use the idea of pinning edges. On a high level, when performing a merge by buying a shortest path, we pin the cheapest $(1/\log n)$-fraction of edges on this path, where pinning an edge means that it will not be deleted in the future, even if the corresponding merge is later revoked. To bound the recourse without harming the approximation, we will guarantee the following.

• $\mathrm{■}$

  The number of pinned edges is linear in $n$ at the end, which means that the total recourse will be bounded by $O(n\log n)$. This is relatively simple: intuitively, we will enforce the set of pinned edges to be acyclic.

• $\mathrm{■}$

  The cost of the pinned edges should always be within a constant factor of the optimum, so that we can still guarantee a constant-factor approximation. To this end, an important step is to bound the total cost of all merges throughout the algorithm by $O(\log n\cdot \mathrm{𝖮𝖯𝖳})$, including those that are later revoked (see the following Step 2 for a detailed discussion). This will bound the total cost of pinned edges by $O(\mathrm{𝖮𝖯𝖳})$, since whenever we buy a path, the cheapest $(1/\log n)$-fraction of its edges, which we pin, have cost at most $(1/\log n)$-fraction of the path cost.

We employ a particular clustering procedure from the offline timed gluttonous algorithm [55]. It proceeds by levels, from $0$ to the top. At each level $i$, it iteratively merges two clusters if their distance is in $[2^i,2^{i+1})$ (the merging cost is at most their distance). Furthermore, the clustering procedure allows some flexibility in choosing the order of level-$i$ merges; intuitively, we prioritize the level-$i$ merges that already existed in the previous arrival.

For the above clustering procedure, we can show that for a fixed level $i$, the cost of all merging operations at this level throughout the algorithm is bounded by $O(\mathrm{𝖮𝖯𝖳})$ using a dual-fitting framework. At a high level, the dual-fitting argument is intuitive: we want to maintain a set of source vertices and obtain a feasible dual solution by growing balls around them. The subtlety in the formal analysis is that choosing (and maintaining) the right source vertices requires exploiting how the offline clustering procedures relate to one another across different arrivals.

Finally, the total merging cost is $O(\log n\cdot \mathrm{𝖮𝖯𝖳})$, since the merges from levels beyond the top $O(\log n)$ will have negligible costs. We emphasize that this total merging cost is not the cost of our online solution. The online solution consists of (i) the output of an offline $O(1)$-approximate algorithm for the current instance, and (ii) the edges pinned up to that point, which have cost $O(\mathrm{𝖮𝖯𝖳})$ as long as the total merging cost is $O(\log n\cdot \mathrm{𝖮𝖯𝖳})$.

We prove this by induction on $i$. Since ${𝒞}_0^{(t-1)}$ is the trivial clustering on the terminal set $V^{(t-1)}$ and ${𝒞}_0^{(t)}$ is the trivial clustering on the terminal set $V^{(t)}$, the base case is true. Now assume for some fixed $i$, ${𝒞}_i^{(t-1)}⪯{𝒞}_i^{(t)}$. We will show ${𝒞}_{i+1}^{(t-1)}⪯{𝒞}_{i+1}^{(t)}$. In other words, our goal is to show that a cluster $C\in {𝒞}_{i+1}^{(t-1)}$ is fully contained in some cluster of ${𝒞}_{i+1}^{(t)}$. To this end, we consider the connected components of $H_i^{(t-1)}$ and the connected components of $H_i^{(t)}$. Note that if some two clusters $C_1,C_2\in {𝒞}_i^{(t-1)}$ have

then, since ${𝒞}_i^{(t-1)}⪯{𝒞}_i^{(t)}$, we also have that for the parent clusters $D_1,D_2\in {𝒞}_i^{(t)}$ which contain $C_1$ and $C_2$ respectively,

Therefore, an edge between $C_1$ and $C_2$ in $H_i^{(t-1)}$ is also an edge between $D_1$ and $D_2$ in $H_i^{(t)}$. So, if a cluster $C\in {𝒞}_{i+1}^{(t-1)}$ results from some connected component $Q$ in $H_i^{(t-1)}$ consisting of $C_1,\mathrm{\dots },C_k$, then there is a corresponding connected component $Q^{\prime }$ of $D_1,\mathrm{\dots },D_k$ in $H_i^{(t)}$ (note that the $D_{\mathrm{\ell }}$ are not necessarily distinct). This proves our inductive step. $◀$

We first construct a virtual solution ${\widehat{F}}^{(t)}$ using virtual edges in the virtual graphs $H_i^{(t)}$ for all $i$. Similarly to the forest-forming procedure in Section 3, for each level $0\le i\le L^{(t)}$, we will pick a virtual spanning forest ${\widehat{F}}_i^{(t)}$ of $H_i^{(t)}$. However, rather than choosing an arbitrary forest as ${\widehat{F}}_i^{(t)}$, we will choose ${\widehat{F}}_i^{(t)}$ more carefully, as we discuss shortly. The virtual solution ${\widehat{F}}^{(t)}={\bigcup }_{0\le i\le L^{(i)}}{\widehat{F}}_i^{(t)}$ is simply the union of virtual spanning forests at all levels.

Inheritable and Inherited Virtual Edges. Before describing how to choose ${\widehat{F}}_t^{(i)}$, we need to introduce the concepts of inheritable/non-inheritable and inherited/non-inherited virtual edges.

For each virtual edge ${\widehat{e}}^{(t-1)}=(C_1,C_2)\in {\widehat{F}}_i^{(t-1)}$, it is inheritable if $C_1,C_2\in {𝒞}_i^{(t-1)}$ are not contained in the same ${𝒞}_i^{(t)}$-cluster (recall that ${𝒞}_i^{(t-1)}⪯{𝒞}_i^{(t)}$ from Lemma 9), otherwise it is non-inheritable.

In the same vein as the proof above, note that if ${\widehat{e}}^{(t-1)}=(C_1,C_2)$ is an inheritable virtual edge in $H_i^{(t-1)}$, then: (1) $C_1,C_2\in {𝒞}_i^{(t-1)}$ are contained in distinct clusters $D_1$ and $D_2$ in ${𝒞}_i^{(t)}$, and (2) . The second property implies , and therefore we will have an edge ${\widehat{e}}^{(t)}\in H_i^{(t)}$ connecting $D_1$ and $D_2$. $◀$

Lemma 10 naturally defines a mapping ${\pi }_i^{(t)}$ from the inheritable virtual edges in ${\widehat{F}}_i^{(t-1)}$ to virtual edges in $H_i^{(t)}$. We define the inherited virtual edges in $H_i^{(t)}$ to be the image set of ${\pi }_i^{(t)}$, and will call the other virtual edges in $H_i^{(t)}$ non-inherited. For each inherited virtual edge ${\widehat{e}}^{(t)}\in H_i^{(t)}$, we fix an arbitrary inheritable virtual edge ${\widehat{e}}^{(t-1)}\in {\widehat{F}}_i^{(t-1)}$ with ${\pi }_i^{(t)}({\widehat{e}}^{(t-1)})={\widehat{e}}^{(t)}$ as the parent of ${\widehat{e}}^{(t)}$, and say that ${\widehat{e}}^{(t)}$ is inherited from its parent ${\widehat{e}}^{(t-1)}$.

Choosing ${\widehat{F}}_t^{(i)}$. Now, we pick the virtual spanning forest ${\widehat{F}}_i^{(t)}$ giving priority to the inherited virtual edges in $H_i^{(t)}$. Formally speaking, we first pick an arbitrary spanning forest ${\widehat{F}}_{\mathrm{inh},i}^{(t)}$ in $H_{\mathrm{inh},i}^{(t)}$, the subgraph of $H_i^{(t)}$ induced by the inherited virtual edges. Then we arbitrarily augment ${\widehat{F}}_{\mathrm{inh},i}^{(t)}$ to be a spanning forest ${\widehat{F}}_i^{(t)}$ of $H_i^{(t)}$.

For better understanding, we emphasize that virtual edges in ${\widehat{F}}_i^{(t)}$ are classified in two ways: inheritable vs. non-inheritable, and inherited (${\widehat{F}}_{\mathrm{inh},i}^{(t)}$) vs. non-inherited (${\widehat{F}}_i^{(t)}\setminus {\widehat{F}}_{\mathrm{inh},i}^{(t)}$). Each inherited virtual edge in ${\widehat{F}}_i^{(t)}$ is inherited from its parent, some inheritable virtual edge in ${\widehat{F}}_i^{(t-1)}$. However, not every inheritable virtual edge in ${\widehat{F}}_i^{(t-1)}$ may serve as the parent of an inherited virtual edge in ${\widehat{F}}_i^{(t)}$.

Note that ${𝒞}_{i+1}^{(t)}$ is exactly the clustering obtained by contracting ${\widehat{F}}_i^{(t)}$ over ${𝒞}_i^{(t)}$ (the meaning of contracting is the same as in Step 2 of the clustering procedure), and we let ${𝒞}_{\mathrm{inh},i}^{(t)}$ denote the clustering obtained by contracting ${\widehat{F}}_{\mathrm{inh},i}$ over ${𝒞}_i^{(t)}$. Then we have the following Lemma 11 which will be useful later.

Assume for contradiction that there exists a cluster $C_{i+1}^{(t-1)}\in {𝒞}_{i+1}^{(t-1)}$ such that $C_{i+1}^{(t-1)}$ intersects two different clusters in ${𝒞}_{\mathrm{inh},i}^{(t)}$.

First, we claim that $C_{i+1}^{(t-1)}$ is $i$-active. Assume the opposite. We must have $C_{i+1}^{(t-1)}\in {𝒞}_i^{(t-1)}$ by the description of the clustering procedure. By Lemma 9, we know

Hence $C_{i+1}^{(t-1)}$ is contained in some cluster in ${𝒞}_{\mathrm{inh},i}^{(t)}$, a contradiction.

Given that $C_{i+1}^{(t-1)}$ is $i$-active, it is the union of several $i$-active clusters in ${𝒞}_i^{(t-1)}$ by the clustering procedure. Then, by ${𝒞}_i^{(t-1)}⪯{𝒞}_{\mathrm{inh},i}^{(t)}$ and the assumption that $C_{i+1}^{(t-1)}$ intersects two different clusters in ${𝒞}_{\mathrm{inh},i}^{(t)}$, there must be two different $i$-active ${𝒞}_i^{(t-1)}$-clusters $C_{i,1}^{(t-1)}$ and $C_{i,2}^{(t-1)}$ inside $C_{i+1}^{(t-1)}$ such that they are contained by different ${𝒞}_{\mathrm{inh},i}^{(t)}$-clusters.

Let $C_{i,1}^{(t)}$ and $C_{i,2}^{(t)}$ be the ${𝒞}_i^{(t)}$-clusters containing $C_{i,1}^{(t-1)}$ and $C_{i,2}^{(t-1)}$ respectively (we use ${𝒞}_i^{(t-1)}⪯{𝒞}_i^{(t)}$ from Lemma 9 again). If $C_{i,1}^{(t)}$ and $C_{i,2}^{(t)}$ are the same, combining it with ${𝒞}_i^{(t)}⪯{𝒞}_{\mathrm{inh},i}^{(t)}$ already leads to a contradiction. Hence we assume $C_{i,1}^{(t)}$ and $C_{i,2}^{(t)}$ are different clusters. Now, we have already known that $C_{i,1}^{(t-1)}$ and $C_{i,2}^{(t-1)}$ are in the same connected component of $H_i^{(t-1)}$ (i.e., they are connected by the virtual spanning forest ${\widehat{F}}_i^{(t-1)}$). From the inheritance relation between ${\widehat{F}}_i^{(t-1)}$-virtual edges and $H_i^{(t)}$-virtual edges, it is straightforward to see that $C_{i,1}^{(t)}$ and $C_{i,2}^{(t)}$ are in the same connected component of $H_{\mathrm{inh},i}^{(t)}$, which means they are contained by the same ${𝒞}_{\mathrm{inh},i}^{(t)}$-cluster, a contradiction. $◀$

In the second phase, we will construct the snapshot $F^{(t)}$ based on the virtual solution ${\widehat{F}}^{(t)}$. A natural attempt is to proceed analogously to the offline forest-forming procedure in Section 3: for each virtual edge $\widehat{e}=(C_1,C_2)\in {\widehat{F}}_i^{(t)}\subseteq {\widehat{F}}^{(t)}$, add into $F^{(t)}$ a $C_1$-$C_2$ shortest path in the metric $ℳ/{𝒞}_i^{(t)}$. This will give a feasible $F^{(t)}$ with good approximation as we discussed in Section 3. However, it gives no control over the recourse: such a shortest path may be made up of many original edges in the original metric $ℳ$.

We fix this issue by pinning edges. Roughly speaking, whenever we add a shortest path, we pin some fraction of its original edges. Pinning an original edge means that we will never remove it from our online solution. We will guarantee two properties of the pinned edges. First, the total cost of pinned edges is always within a constant factor of the optimum, so that the online solution can achieve a constant competitive ratio. Second, the number of pinned edges grows linearly in $t$, so that we can achieve low recourse by charging the number of original edge insertions to the number of pinned edges. We now formalize this argument.

As demands arrive, we will maintain a growing set $A$ of pinned edges. Our job in the current arrival $t$ is to assign to each virtual edge ${\widehat{e}}^{(t)}\in {\widehat{F}}^{(t)}$ a set of original edges in $ℳ$, denoted by $E_{\mathrm{orig}}({\widehat{e}}^{(t)})$. From the previous arrival $t-1$, we are already given the pinned edge set $A^{(t-1)}$ and the original edge set $E_{\mathrm{orig}}({\widehat{e}}^{(t-1)})$ of every virtual edge ${\widehat{e}}^{(t-1)}\in {\widehat{F}}^{(t-1)}$. Meanwhile, we will also update the pinned edge set from $A^{(t-1)}$ to $A^{(t)}$. The original solution is then

For each inherited virtual edge ${\widehat{e}}^{(t)}\in {\widehat{F}}^{(t)}$, its original edge set is simply

where ${\widehat{e}}^{(t-1)}\in {\widehat{F}}^{(t-1)}$ is the parent of ${\widehat{e}}^{(t)}$. As for pinning, on a high level, we add a $1/\lambda$ fraction of the original edges to $A^{(t)}$ (selecting the cheapest ones); if there are fewer than $\lambda$ many, we use a buffer set. More precisely, the original edge sets of the non-inherited virtual edges and the update from $A^{(t-1)}$ to $A^{(t)}$ are given by the following algorithm.

We note that we define the buffer $B$ to be a multiset just for ease of analysis. Defining $B$ as a set instead will not affect the correctness.

Finally, to enhance understanding, we outline our entire online algorithm in Algorithm 2.

If ${\widehat{e}}^{(t)}$ is a non-inherited virtual edge, this statement directly follows from Lines 4 and 5 of Algorithm 1. Concretely, at the moment $E_{\mathrm{orig}}$ is defined at Line 5, $C_1^{(t)}$ and $C_2^{(t)}$ clearly belong to the same vertex in $(ℳ/{𝒞}_i^{(t)})/(A^{(t)}\cup E_{\mathrm{orig}}({\widehat{e}}^{(t)}))$ by definition. Therefore, at the end of arrival $t$, since $A^{(t)}$ only grows during Algorithm 1, the statement also holds.

The argument for an inherited virtual edge ${\widehat{e}}^{(t)}$ is similar, but we need induction to formally prove it. Assume inductively that the statement of Lemma 12 holds for all virtual edges in ${\widehat{F}}^{(t-1)}$. Let ${\widehat{e}}^{(t-1)}=(C_1^{(t-1)},C_2^{(t-1)})\in {\widehat{F}}_i^{(t-1)}$ be the parent of ${\widehat{e}}^{(t)}$, which means $C_1^{(t)}\supseteq C_1^{(t-1)}$, $C_2^{(t)}\supseteq C_2^{(t-1)}$ and $E_{\mathrm{orig}}({\widehat{e}}^{(t)})=E_{\mathrm{orig}}({\widehat{e}}^{(t-1)})$. Then the statement holds for ${\widehat{e}}^{(t)}$ by the induction hypothesis and because ${𝒞}_i^{(t-1)}⪯{𝒞}_i^{(t)}$ $◀$

And so, since ${\widehat{F}}_i^{(t)}$ virtually connects up demands in the arrived demand set (by Observation 6), we know that $F_i^{(t)}$ will be a feasible solution.

Observe that whenever we pin several edges at Line 7 or one edge at Line 12, the new pinned edges do not form a cycle with the existing pinned edges on the terminal set $V^{(t)}$. Hence at the end $A^{(n)}$ is a forest on $V^{(n)}$, which implies that $|A^{(n)}|\le |V^{(n)}|-1=2n-1$. $◀$

Next, we charge the total size of original edge sets of non-inherited virtual edges (non-inherited original edge sets for short) to the number of pinned edges. In every execution of Line 7, we charge each new pinned edge a fee of $10\lambda$ units to account for $|B|+|E_{\mathrm{orig}}({\widehat{e}}^{(t)})|$, which is feasible because

when $|E_{\mathrm{orig}}({\widehat{e}}^{(t)})|\ge \lambda$ and (guaranteed by Line 11). In every execution of Line 12, again charge the new pinned edge a fee of $10\lambda$ units to account for $|B|$, which is available because $|B|\le 2\lambda$ (right before Line 10, the buffer $B$ has size less than $\lambda$, and the current $E_{\mathrm{orig}}({\widehat{e}}^{(t)})$ has size less than $\lambda$). Finally, observe that every non-inherited original edge set is accounted for in the charging argument (either directly or via the buffer $B$), except for those remaining in the buffer $B$ at the end of each arrival (at these moments, ). Therefore, we have

The forest-forming cost can be interpreted as the cost of the offline Steiner forest algorithm introduced in Section 3, which can be directly bounded by Lemma 7.

Formally, for each level $i$ and each virtual edge ${\widehat{e}}^{(n)}\in {\widehat{F}}_i^{(n)}$, we have

To see this, we trace ${\widehat{e}}^{(n)}$ back through the inheritance relation until reaching a non-inherited virtual edge ${\widehat{e}}^{(t)}=(C_1,C_2)\in {\widehat{F}}_i^{(t)}$ in some arrival $t\le n$. At the moment when $E_{\mathrm{orig}}({\widehat{e}}^{(t)})$ is defined on Lines 4 and 5 of Algorithm 1, we have

where the last inequality is by ${\widehat{F}}_i^{(t)}\subseteq H_i^{(t)}$ and the definition of $H_i^{(t)}$. The inheritance relation implies $E_{\mathrm{orig}}({\widehat{e}}^{(n)})=E_{\mathrm{orig}}({\widehat{e}}^{(t)})$, so we get the desired bound (1).

Given (1), we bound the forest-forming cost by

where the equality is by $|{\widehat{F}}_i^{(n)}|=|{𝒞}_i^{(n)}|-|{𝒞}_{i+1}^{(n)}|$ and the last inequality is by Lemma 7.

Algorithm 1 pins roughly a $(1/\lambda )$-fraction of edges from the non-inherited original edge sets, so naturally the first step is to bound the total cost of non-inherited original edge sets.

We say that a non-inherited original edge set is from level $i$ if its corresponding non-inherited virtual edge is from ${\widehat{F}}_i^{(t)}$ for some $t$. Theorem 14 above shows that for each level $i$, the total cost of non-inherited original edge sets summed over all arrivals is bounded by $O(\mathrm{𝖮𝖯𝖳})$ (note that each non-inherited original edge set has cost at most $2^{i+1}$ as we argued in (2)).

We prove Theorem 14 in Section 4.6 below. Given Theorem 14, the intuition for bounding the pinning cost is as follows. If we assume that there are $O(\log n)$ levels, then Theorem 14 shows that the total cost of non-inherited original edge sets is $O(\log n\cdot \mathrm{𝖮𝖯𝖳})$, so the pinning cost can be bounded by $O(\log n\cdot \mathrm{𝖮𝖯𝖳}/\lambda )$ since we pinned roughly a $(1/\lambda )$ fraction. Without the assumption of $O(\log n)$ levels, the intuition is that non-inherited original edge sets not from the top $O(\log n)$ levels have negligible costs. We formalize this intuition as follows.

To see $\mathrm{𝖼𝗈𝗌𝗍}(A^{(n)})\le O(\mathrm{𝖮𝖯𝖳})$, by Lemma 13 it suffices to show $\mathrm{𝖼𝗈𝗌𝗍}(A^{\prime })\le O(\mathrm{𝖮𝖯𝖳})$, where $A^{\prime }=\{e\mid e\in A^{(n)}\text{ s.t. }\mathrm{𝖼𝗈𝗌𝗍}(e)>\mathrm{𝖮𝖯𝖳}/n\}$ are pinned edges with non-negligible costs. Note that $A$ will only grow at Lines 7 and 12 in Algorithm 1.

Line 7. Consider an execution of Line 7 that brings new $A^{\prime }$-pinned edges. The current non-inherited original edge set $E_{\mathrm{orig}}({\widehat{e}}^{(t)})$ must come from the top $\lceil \log n\rceil +2$ levels (i.e., the current level $i$ is between $L^{(n)}-\lceil \log n\rceil -1$ and the maximum level $L^{(n)}$). Otherwise, we have $\mathrm{𝖼𝗈𝗌𝗍}(E_{\mathrm{orig}}({\widehat{e}}^{(t)}))\le 2^{i+1}\le 2^{L^{(n)}-1}/n\le \mathrm{𝖮𝖯𝖳}/n$ (note that $2^{L^{(n)}-1}\le \mathrm{𝖮𝖯𝖳}$ by the definition of the function $\mathrm{𝗅𝖾𝗏𝖾𝗅}$), and any pinned edge from $E_{\mathrm{orig}}({\widehat{e}}^{(t)})$ would have negligible cost. Furthermore, the algorithm guarantees that the total cost of new $A^{\prime }$-pinned edges from this execution is at most $\mathrm{𝖼𝗈𝗌𝗍}(E_{\mathrm{orig}}({\widehat{e}}^{(t)}))/\lambda$.

Line 12. Suppose an execution of Line 12 brings a new $A^{\prime }$-pinned edge. Note that at this moment, the buffer $B$ is the multiset union of several non-inherited original edge sets, all of which come from the top $\lceil \log n\rceil +2$ levels by the same argument as in the previous case. Again, the algorithm guarantees the cost of this new $A^{\prime }$-pinned edge is at most $\mathrm{𝖼𝗈𝗌𝗍}(B)/\lambda$.