Nearly-Optimal Algorithm for Non-Clairvoyant Service with Delay

As part of our algorithm, we formulate and solve a Steiner tree problem. In Steiner tree, one is given a graph with edge costs and a set of terminal nodes. The goal is to buy an edge subset of minimal cost that connects the terminals. With terminals $V$, and assuming that the graph is known from context, we use ${\mathrm{ST}}^{\ast }(V)$ to denote the optimal cost of a solution. We also sometimes refer to the (equivalent) rooted version, in which the terminals must be connected to a designated root node $r$; here, we use ${\mathrm{ST}}^{\ast }(V;r)$ to denote the optimal cost.

In the prize-collecting variant of the (rooted) Steiner tree problem, we are also given a penalty function $\pi$ mapping from each terminal to a non-negative penalty; we write the prize-collecting input as $(Q,\pi ;r)$. The algorithm must connect terminals to the root by buying edges, and must pay the penalty for unconnected terminals. The goal of the algorithm is to minimize the sum of edge costs and penalty costs; we write ${\mathrm{PCST}}^{\ast }(Q,\pi ;r)$ to refer to the optimal solution to the input $(Q,\pi ;r)$. A Lagrangian prize-collecting algorithm is an algorithm that has different approximation ratios w.r.t. these two costs, such that it is 1-approximate on penalty costs. Specifically, Goemans and Williamson [23] presented the following algorithm for prize-collecting Steiner tree.

In [34], a simple procedure is presented that converts a Lagrangian prize-collecting procedure into a procedure which identifies a solution to a maximal subset of requests subject to a budget per request. Combining this result with the algorithm of [23] yields Lemma 4, which introduces the procedure PCSolve used in our algorithm.

The algorithm maintains for every pending request $q$ a level ${\mathrm{\ell }}_q$, which is initially $-\mathrm{\infty }$. A service $\lambda$ also has a level ${\mathrm{\ell }}_{\lambda }$, which determines its budget for serving requests. As services occur, they may increase the levels of requests. The algorithm also maintains for request $q$ a pointer ${\mu }_q$ to the last service that increased the level of $q$. (A fine point, as seen in the algorithm, is that a service may also appear in the pointer ${\mu }_q$ only for “attempting” to increase ${\mathrm{\ell }}_q$.) Finally, overloading notation, each service $\lambda$ also has a pointer ${\mu }_{\lambda }$ that points to a prior service; this pointer is equal to the pointer ${\mu }_q$ for some request $q$ considered by $\lambda$.

The algorithm maintains a residual delay counter $g_{v,\mathrm{\ell }}$ for every location $v$ and level $\mathrm{\ell }$; for time $t$, we define $g_{v,\mathrm{\ell }}(t)$ to be the value of $g_{v,\mathrm{\ell }}$ at time $t$. This counter grows with the delay cost incurred by level-$\mathrm{\ell }$ requests on $v$. In addition, the counters are occasionally decreased by services made by the algorithm; this can be interpreted as the service “paying” for incurred delay out of its budget. Positive counters correspond to incurred delay that has not yet been handled; such counters can trigger a service, in the manner we now describe.

At any time $t$, and for every level $\mathrm{\ell }$, the algorithm considers positive residual delay counters of levels at most $\mathrm{\ell }$ inside $B(a(t),2^{\mathrm{\ell }})$. Specifically, it considers the total unhandled residual delay of requests of level at most $\mathrm{\ell }$ inside the ring $B(a(t),2^{\mathrm{\ell }})\setminus B(a(t),2^{\mathrm{\ell }-1})$, plus unhandled residual delay of requests of level exactly $\mathrm{\ell }$ inside the internal ball $B(a(t),2^{\mathrm{\ell }-1})$. This forms a dome-like structure, as shown in Figure 1. The algorithm waits until a dome corresponding to some level $\mathrm{\ell }$ becomes critical, i.e., has a lot of unhandled residual delay, and then starts a service. These notions are formalized in Definition 5.

Whenever dome $\mathrm{\ell }$ becomes critical, we start a service $\lambda$ of level $\mathrm{\ell }+4$. (If more than one dome is critical at the same time, we handle the dome of the largest level first.) The service first considers whether the dome has any positive residual delay from the inner ball $B(a_{\lambda },2^{\mathrm{\ell }-1})=B(a_{\lambda },2^{{\mathrm{\ell }}_{\lambda }-5})$. If not, the service $\lambda$ is called primary. Otherwise, consider a location $v$ of the inner ball that contributes positive residual delay to the dome; it must be that $g_{v,\mathrm{\ell }}>0$, which implies (through Proposition 9) that there exists a level-$\mathrm{\ell }$ pending request on $v$. The service arbitrarily chooses such a request ${\sigma }_{\lambda }$, and observes the last service to modify the level of the request, i.e., ${\mu }_{{\sigma }_{\lambda }}$; denote this service by ${\lambda }^{\prime }$. Depending on ${\lambda }^{\prime }$, the algorithm decides if the service will invest for the future (“secondary” service) or act greedily (“tertiary” service). Specifically, the algorithm maintains a counter $\beta ({\lambda }^{\prime })$ for the number of times ${\lambda }^{\prime }$ has triggered tertiary services; if the counter is low, $\lambda$ becomes tertiary and increments this counter; otherwise, $\lambda$ will be secondary. After deciding if a service is primary, secondary, or tertiary, the algorithm zeroes all positive residual delay on locations in $B(a_{\lambda },2^{{\mathrm{\ell }}_{\lambda }})$ of levels up to ${\mathrm{\ell }}_{\lambda }$; in particular, this zeroes the residual delay that triggered $\lambda$.

Next, if the service is tertiary, it simply moves the server to ${\sigma }_{\lambda }$ and back, concluding the service. Otherwise, $\lambda$ is primary or secondary, and thus invests in serving pending requests, through the method ServeEligible. In ServeEligible, the service considers the subset of locations $V_{\lambda }$ inside $B(a_{\lambda },2^{{\mathrm{\ell }}_{\lambda }})$ on which there are pending requests. To each location in $V_{\lambda }$, the algorithm assigns a budget of $x_{\lambda }=2^{{\mathrm{\ell }}_{\lambda }}/\sqrt{\left|V_{\lambda }\right|}$ to visiting each such location; the locations $V_{\lambda }$, together with their budgets as penalties, are transferred to PCSolve as a prize-collecting Steiner tree input (where the root is the current location of the server $a_{\lambda }$). PCSolve outputs a tree connecting some locations $Q_{\lambda }^{\circ }\subseteq V_{\lambda }$ to $a_{\lambda }$; this tree is then traversed by the server in a DFS fashion, visiting $Q_{\lambda }^{\circ }$ and ending at $a_{\lambda }$. For the remaining locations $V_{\lambda }\setminus Q_{\lambda }^{\circ }$, where PCSolve pays the penalty, the algorithm decreases the delay counters for those locations by $x_{\lambda }$. On those locations, the algorithm makes pending requests of level at most ${\mathrm{\ell }}_{\lambda }$ point to $\lambda$, and upgrades their level to ${\mathrm{\ell }}_{\lambda }$.

Finally, for primary services, the algorithm may move the server to a new location $a_{\lambda }^{\prime }$. Recall that $\lambda$ starts upon dome ${\mathrm{\ell }}_{\lambda }-4$ becoming critical; if the majority of the residual delay making dome ${\mathrm{\ell }}_{\lambda }-4$ critical occurs inside a small-radius ball (specifically, radius $2^{{\mathrm{\ell }}_{\lambda }-8}$), then the center of this ball becomes the new location $a_{\lambda }^{\prime }$, at which the server rests at the end of the service.

The non-clairvoyant algorithm for online service with delay is given in Algorithm 1, and the ServeEligible method appears in Algorithm 2. We henceforth focus on analyzing Algorithm 1 and proving Theorem 1.

First, observing Line 9 of Algorithm 2, we note that if for request $q$ we have ${\mu }_q=\lambda$, then it must be the case that ${\mathrm{\ell }}_q={\mathrm{\ell }}_{\lambda }$ at that time. Note that $\lambda$ is only certified by some ${\lambda }^{\prime }\in {\mathrm{\Lambda }}^{\text{2}}$ if ${\mu }_{{\sigma }_{{\lambda }^{\prime }}}=\lambda$, and thus ${\mathrm{\ell }}_{{\sigma }_{{\lambda }^{\prime }}}={\mathrm{\ell }}_{\lambda }$ at $t_{{\lambda }^{\prime }}$; but, ${\mathrm{\ell }}_{{\lambda }^{\prime }}={\mathrm{\ell }}_{{\sigma }_{{\lambda }^{\prime }}}+4$ at $t_{{\lambda }^{\prime }}$, proving the second item. Moreover, note that ${\sigma }_{{\lambda }^{\prime }}\in V_{\lambda }$, and thus $\delta (a_{\lambda },{\sigma }_{{\lambda }^{\prime }})\le 2^{{\mathrm{\ell }}_{\lambda }}$. In addition, since ${\sigma }_{{\lambda }^{\prime }}\in B(a_{{\lambda }^{\prime }},2^{{\mathrm{\ell }}_{{\lambda }^{\prime }}-5})$, we have $\delta (a_{{\lambda }^{\prime }},{\sigma }_{{\lambda }^{\prime }})\le 2^{{\mathrm{\ell }}_{{\lambda }^{\prime }}-5}=2^{{\mathrm{\ell }}_{\lambda }-1}$. The triangle inequality thus implies $\delta (a_{\lambda },a_{{\lambda }^{\prime }})\le 2^{{\mathrm{\ell }}_{\lambda }}+2^{{\mathrm{\ell }}_{\lambda }-1}\le 2^{{\mathrm{\ell }}_{\lambda }+1}$, proving the third item.

We now prove the first item, i.e., the uniqueness of ${\lambda }^{\prime }$. Suppose, for contradiction, that a certified service $\lambda \in {\mathrm{\Lambda }}^{\text{c}}$ is certified by two services ${\lambda }^{\prime },{\lambda }^{\prime \prime }\in {\mathrm{\Lambda }}^{\text{2}}$, and assume without loss of generality that ${\lambda }^{\prime }$ occurs before ${\lambda }^{\prime \prime }$. We prove that after ${\lambda }^{\prime }$, there remains no pending request $q$ with ${\mu }_q=\lambda$, and thus ${\lambda }^{\prime \prime }$ cannot certify $\lambda$ later on. Indeed, consider such a request $q$ immediately before ${\lambda }^{\prime }$; it holds that $q\in V_{\lambda }\subseteq B(a_{\lambda },2^{{\mathrm{\ell }}_{\lambda }})$, and it must also be the case that ${\mathrm{\ell }}_q={\mathrm{\ell }}_{\lambda }$ at that time. But, we’ve shown that $\delta (a_{\lambda },a_{{\lambda }^{\prime }})\le 2^{{\mathrm{\ell }}_{\lambda }+1}$, and thus $B(a_{\lambda },2^{{\mathrm{\ell }}_{\lambda }})\subseteq B(a_{{\lambda }^{\prime }},2^{{\mathrm{\ell }}_{\lambda }}+4)=B(a_{{\lambda }^{\prime }},2^{{\mathrm{\ell }}_{{\lambda }^{\prime }}})$. Thus, $q\in V_{{\lambda }^{\prime }}$, and will either be served by ${\lambda }^{\prime }$ or have ${\mu }_q$ be set to ${\lambda }^{\prime }$, in contradiction to having ${\mu }_q=\lambda$ at $t_{{\lambda }^{\prime \prime }}$. $◀$

The proof of Proposition 8 is in Appendix B.

We prove this by induction as time advances, noting that the proposition holds at time $0$ (before any requests are released). Note that $g_{v,\mathrm{\ell }}(t)$ grows at the same rate as the delay of pending requests of level $\mathrm{\ell }$ on $v$, and thus delay growth cannot break the invariant. In addition, counter decreases in services cannot break the invariant. The only risky event is when a request of level $\mathrm{\ell }$ is upgraded or completed. But, this only happens in a service $\lambda$ such that ${\mathrm{\ell }}_{\lambda }\ge \mathrm{\ell }$ and $v\in B(a_{\lambda },2^{{\mathrm{\ell }}_{\lambda }})$. Note that in such services, Line 17 of Algorithm 1 ensures that $g_{v,\mathrm{\ell }}$ is non-positive after the service, maintaining the invariant. $◀$

Note that the server only moves to $a_{\lambda }^{\prime }$ when $\lambda$ is primary. In this case, it holds that $V_{\lambda }^{†}\cap B(a_{\lambda },2^{{\mathrm{\ell }}_{\lambda }-5})=\mathrm{\varnothing }$. But, due to Proposition 9, this implies that $g_{v,{\mathrm{\ell }}_{\lambda }-4}(t)\le 0$ for every $v\in B(a_{\lambda },2^{{\mathrm{\ell }}_{\lambda }-5})$; thus, for such $v$ we have $y_{{\mathrm{\ell }}_{\lambda }-4}(v,t)=0$, and thus $V_{\lambda }^{†}$ is contained in the ring $B(a_{\lambda },2^{{\mathrm{\ell }}_{\lambda }-4})\setminus B(a_{\lambda },2^{{\mathrm{\ell }}_{\lambda }-5})$. But, from the definition of $a_{\lambda }^{\prime }$, $B(a_{\lambda }^{\prime },2^{{\mathrm{\ell }}_{\lambda }-8})$ must contain a point from $V_{\lambda }^{†}$, which completes the proof. $◀$

For a service $\lambda$, define the cost of the service, denoted $c\left(\lambda \right)$, to be the total movement of the server during $\lambda$ plus the total amount by which the service decreases counters $g_{v,\mathrm{\ell }}$.

To prove the proposition, we just have to prove that the total delay incurred by the algorithm is upper-bounded by the total amount by which counters are decreased in the algorithm. First, recall the assumption that the delay of requests tends to infinity as time advances; thus, every request is eventually served by the algorithm. Thus, once all requests are served, Proposition 9 implies that $g_{v,\mathrm{\ell }}\le 0$ for every $v\in G$ and level $\mathrm{\ell }$, which completes the proof. $◀$

The following observation results from the fact that every counter $g_{v,\mathrm{\ell }}$ is counted in exactly one dome (and can also easily be seen in Figure 1).

Applying Proposition 11, it is enough to bound ${\sum }_{\lambda \in \mathrm{\Lambda }}c\left(\lambda \right)$. We first bound the cost of tertiary services ${\sum }_{\lambda \in {\mathrm{\Lambda }}^{\text{3}}}c\left(\lambda \right)$. Consider a tertiary service $\lambda \in {\mathrm{\Lambda }}^{\text{3}}$; it incurs the following costs:

1. 1.

   It zeroes any positive counters $g_{v,\mathrm{\ell }}$ for every $v\in B(a_{\lambda },2^{{\mathrm{\ell }}_{\lambda }})$ and $\mathrm{\ell }\le {\mathrm{\ell }}_{\lambda }$. The cost of this is at most

   $$\sum _{v\in B(a_{\lambda },2^{{\mathrm{\ell }}_{\lambda }})}\sum _{\mathrm{\ell }\le {\mathrm{\ell }}_{\lambda }}{(g_{v,\mathrm{\ell }})}^{+}=\sum _{\mathrm{\ell }\le {\mathrm{\ell }}_{\lambda }}{Y}_{\mathrm{\ell }}\le 2^{{\mathrm{\ell }}_{\lambda }+3},$$

   where the equality is due to Observation 12, and the inequality is due to Proposition 8 and summing a geometric sequence.

2. 2.

   It moves the server from $a_{\lambda }$ to ${\sigma }_{\lambda }$ and back (Line 19 of Algorithm 1). Since ${\sigma }_{\lambda }\in B(a_{\lambda },2^{{\mathrm{\ell }}_{\lambda }-4})$, the cost of this is at most $2^{{\mathrm{\ell }}_{\lambda }-3}$.

Overall, the cost of a tertiary service $\lambda$ is $O(2^{{\mathrm{\ell }}_{\lambda }})$.

Now, consider a non-tertiary service $\lambda \in {\mathrm{\Lambda }}^{\text{1}}\cup {\mathrm{\Lambda }}^{\text{2}}$; there are at most $2\cdot \sqrt{\left|V_{\lambda }\right|}+1$ tertiary services assigned to ${\lambda }^{\prime }$, as each such service raises $\beta (\lambda )$ by $1$ and $\beta (\lambda )$ does not exceed $2\cdot \sqrt{\left|V_{\lambda }\right|}+1$; note that $2\cdot \sqrt{\left|V_{\lambda }\right|}+1=O(\sqrt{k})$. Moreover, for a tertiary service ${\lambda }^{\prime }$ assigned to $\lambda$ we have ${\mathrm{\ell }}_{{\lambda }^{\prime }}={\mathrm{\ell }}_{\lambda }+4$. Overall, we have that the cost of tertiary services is $O(\sqrt{k})\cdot {\sum }_{\lambda \in {\mathrm{\Lambda }}^{\text{1}}\cup {\mathrm{\Lambda }}^{\text{2}}}{2}^{{\mathrm{\ell }}_{\lambda }}$.

Next, we bound the cost of non-tertiary services. The cost of a service $\lambda \in {\mathrm{\Lambda }}^{\text{1}}\cup {\mathrm{\Lambda }}^{\text{2}}$ consists of the following terms:

1. 1.

   It zeroes positive counters $g_{v,\mathrm{\ell }}$ for every $v\in B(a_{\lambda },2^{{\mathrm{\ell }}_{\lambda }})$ and $\mathrm{\ell }\le {\mathrm{\ell }}_{\lambda }$. This cost can be bounded by $O(1)\cdot 2^{{\mathrm{\ell }}_{\lambda }}$, using the same argument as for tertiary services.

2. 2.

   In Algorithm 2, the algorithm moves the server (Line 5) and decreases counters (Line 10). From the guarantee of PCSolve in Lemma 4, the cost of moving the server is at most $2\cdot 2\cdot x_{\lambda }\cdot \left|Q_{\lambda }^{\circ }\right|$; the cost of decreasing counters is $(\left|V_{\lambda }\right|-\left|Q_{\lambda }^{\circ }\right|)\cdot x_{\lambda }$. Overall, the cost of this item is at most $O(1)\cdot \left|V_{\lambda }\right|\cdot x_{\lambda }$, which is at most $O(1)\cdot 2^{{\mathrm{\ell }}_{\lambda }}\cdot \sqrt{\left|V_{\lambda }\right|}$. Using the fact that $\left|V_{\lambda }\right|\le k$, the cost of this item is at most $O(\sqrt{k})\cdot 2^{{\mathrm{\ell }}_{\lambda }}$.

3. 3.

   In Line 23 of Algorithm 1, the server might move to a new location $a_{\lambda }^{\prime }$. However, $\delta (a_{\lambda },a_{\lambda }^{\prime })\le 2^{{\mathrm{\ell }}_{\lambda }-4}+2^{{\mathrm{\ell }}_{\lambda }-8}$ due to Proposition 10. Thus, the cost of this movement is also $O(1)\cdot 2^{{\mathrm{\ell }}_{\lambda }}$.

Overall, it holds that $c\left(\lambda \right)\le O(\sqrt{k})\cdot 2^{{\mathrm{\ell }}_{\lambda }}$; combining this with the bound for tertiary services, we get

Finally, we bound ${\sum }_{\lambda \in {\mathrm{\Lambda }}^{\text{2}}}{2}^{{\mathrm{\ell }}_{\lambda }}\le O(1){\sum }_{\lambda \in {\mathrm{\Lambda }}^{\text{c}}}{2}^{{\mathrm{\ell }}_{\lambda }}$, which completes the proof. Consider a secondary service $\lambda \in {\mathrm{\Lambda }}^{\text{2}}$, which certifies some prior service ${\lambda }^{\prime }={\mu }_{\lambda }$. Through Proposition 7, it holds that ${\mathrm{\ell }}_{{\lambda }^{\prime }}={\mathrm{\ell }}_{\lambda }-4$, and thus $2^{{\mathrm{\ell }}_{\lambda }}\le O(1)\cdot 2^{{\mathrm{\ell }}_{{\lambda }^{\prime }}}$. Again through Proposition 7, it holds that ${\lambda }^{\prime }$ is only certified once (by $\lambda$); thus, summing over secondary services yields

which combined with Equation 1 completes the proof. $◀$

A charging shape is a shape in the metric space that contains some edges and “parts” of edges. (For the sake of this definition, an edge $e$ can be partitioned into parts whose weights sum up to $c\left(e\right)$.)

A charging ball centered at $v$ of radius $r$ – which, overloading notation, we denote $B(v,r)$ – is a charging shape such that:

• $\mathrm{■}$

  If both $u,w$ are in $B(v,r)$ then $B(v,r)$ contains the entire edge $\{u,w\}$.

• $\mathrm{■}$

  If $u\in B(v,r)$ but $w\notin B(v,r)$, then $B(v,r)$ contains the part of $\{u,w\}$ connected to $u$ of weight $r-\delta (v,u)$.

A charging cylinder is a pair $(B,I)$ where $I$ is a time interval and $B$ is a charging shape.

We say that a set of charging shapes is disjoint if the parts of edges that appear in different charging shapes do not intersect. We say that a set of charging cylinders is disjoint if for every time $t$ it holds that the charging shapes of the cylinders whose time intervals contain $t$ are disjoint.

For a set of edges $E^{\prime }\subseteq E$ and charging shape $B$, we define $c\left(E^{\prime }\cap B\right)$ to be the total weight of edges in $E^{\prime }$ that appear in $B$. For a cylinder $\gamma =(B,I)$, we define $c\left(\text{OPT}\cap \gamma \right)$ (called the intersection of OPT with $\gamma$) to be the total weight of edges in $E^{\prime }$ that appear in $B$, where $E^{\prime }$ is the set of edges traversed by OPT at least once during $I$.

Theorem 14 is due to [35], and is used to relate the total intersection of the cylinder set we construct to the cost of the optimal solution. The intuition for the theorem is the following: suppose we are given a set of cylinders $\mathrm{\Gamma }$ whose shapes are balls centered at $N$ points. One can replace every such charging ball of radius $r$ with a perforated charging ball, from which balls of small radius $\mathrm{\Theta }(r/N^2)$ are removed around each of the $N$ points; let ${\mathrm{\Gamma }}^{\prime }$ be the set of cylinders after this perforation process. In ${\mathrm{\Gamma }}^{\prime }$, two cylinders whose shapes are (perforated) charging balls with radii $r_1,r_2$ where $r_1\le O(r_2/N^2)$ are guaranteed to be disjoint. Suppose that in the original set $\mathrm{\Gamma }$, every two cylinders with radii within a constant factor from each other are also disjoint; after the perforation, we can partition ${\mathrm{\Gamma }}^{\prime }$ into $\mathrm{\Theta }(\log N)$ disjoint classes. This bounds the intersection of ${\mathrm{\Gamma }}^{\prime }$ with OPT by at most $\mathrm{\Theta }(\log N)\cdot \text{OPT}$. Moreover, one can observe that this perforation of a cylinder’s shape decreases its intersection with OPT by at most a constant times the charging ball’s radius; this relates the intersection of $\mathrm{\Gamma }$ with OPT to the intersection of ${\mathrm{\Gamma }}^{\prime }$ with OPT. For more intuition regarding cylinders and Theorem 14, see Figure 2.

Through constructing and analyzing such cylinders, we prove the following lemmas.

The proof of Lemma 15 appears in Appendix A, while the proof of Lemma 16 appears in the remainder of this section. We now note that given these lemmas, the proof of the main theorem is complete.

The proof is immediate from Lemma 13, Lemma 15 and Lemma 16. $◀$

The remainder of this section proves Lemma 16. For every service $\lambda \in {\mathrm{\Lambda }}^{\text{c}}$, we denote by ${\mathrm{\Lambda }}_{\lambda }$ the set of tertiary services assigned to $\lambda$. We also define ${\mathrm{\Sigma }}_{\lambda }:=\left\{{\sigma }_{{\lambda }^{\prime }}\right|{\lambda }^{\prime }\in {\mathrm{\Lambda }}_{\lambda }\}$; note that ${\mathrm{\Sigma }}_{\lambda }\subseteq E_{\lambda }$. Finally, we define ${\mathrm{\Sigma }}_{\lambda }^{\circ }:=V({\mathrm{\Sigma }}_{\lambda })$.

First, we study the size of the set ${\mathrm{\Sigma }}_{\lambda }^{\circ }$.

First, note that $\left|{\mathrm{\Sigma }}_{\lambda }\right|$ is exactly the final value of the counter $\beta (\lambda )$, as each tertiary service assigned to $\lambda$ increases $\beta (\lambda )$ by 1 (Line 20 of Algorithm 1). A service assigned to $\lambda$ will only be tertiary if ; otherwise, it would be secondary. Thus, the final value of the counter is at most $\lceil 2\sqrt{\left|V_{\lambda }\right|}\rceil$. However, we know that a secondary service is assigned to $\lambda$, as $\lambda \in {\mathrm{\Lambda }}^{\text{c}}$. Thus, the final value of $\beta (\lambda )$ is exactly $\lceil 2\sqrt{\left|V_{\lambda }\right|}\rceil$, completing the proof. $◀$

To prove that the intersection of a certified cylinder with the optimal solution is sufficiently large, we first restate a proposition from [35]. Intuitively, it states that if the set of requested terminals in a Steiner tree input is concentrated in a ball, a constant fraction of the cost required for connecting them must be incurred within a padded version of the ball, whose radius is larger by a constant factor.

We observe charging triplets of the form $(v,\mathrm{\ell },I)$, where $v$ is a location, $\mathrm{\ell }$ is a level, and $I$ is a time interval. Every certified service $\lambda \in {\mathrm{\Lambda }}^{\text{c}}$ owns triplets. Specifically, for every service $\lambda \in {\mathrm{\Lambda }}^{\text{c}}$, location $v\in V_{\lambda }^{\ast }$, and ${\lambda }_v$ the tertiary service assigned to $\lambda$ where ${\sigma }_{{\lambda }_v}\in v$, we say that $\lambda$ owns the triplet $(v,{\mathrm{\ell }}_{\lambda },I_v)$, where $I_v=[t_{\lambda },t_{{\lambda }_v}]$ be the time interval between $\lambda$ and the service ${\lambda }_v$. We now claim the following:

1. 1.

   If $\lambda$ owns triplet $v,\mathrm{\ell },I$, then a delay of at least $x_{\lambda }$ is incurred by requests of level $\mathrm{\ell }$ on $v$ during $I$. Moreover, these requests are pending in the optimal solution during the interval $I$.

2. 2.

   No two triplets intersect. That is, there are no two services ${\lambda }_1,{\lambda }_2\in {\mathrm{\Lambda }}^{\text{c}}$ such that ${\lambda }_1$ owns $(v,\mathrm{\ell },I_1)$, ${\lambda }_2$ owns $(v,\mathrm{\ell },I_2)$ and $I_1\cap I_2\ne \mathrm{\varnothing }$.

The first claim implies that the optimal solution incurs a delay cost of $D_{\mathrm{c},\lambda }^{\ast }$ per service $\lambda \in {\mathrm{\Lambda }}^{\text{c}}$, and the second claim implies that no delay cost is charged twice. Together, these two claims complete the proof.

Fix service $\lambda \in {\mathrm{\Lambda }}^{\text{c}}$, location $v\in V_{\lambda }^{\ast }$, and tertiary service ${\lambda }_v$ assigned to $\lambda$ where ${\sigma }_{{\lambda }_v}\in v$; let $I_v=[t_{\lambda },t_{{\lambda }_v}]$, and set $\mathrm{\ell }:={\mathrm{\ell }}_{\lambda }$. As $v\in {\mathrm{\Sigma }}_{\lambda }^{\circ }\subseteq V_{\lambda }$, it holds immediately after $\lambda$ that $g_{v,{\mathrm{\ell }}_{\lambda }}\le -x_{\lambda }$ (due to Line 17 of Algorithm 1 and Line 10 of Algorithm 2). However, at $t_{{\lambda }_v}$, it holds that $y_{{\mathrm{\ell }}_{{\lambda }_v}-4}\left(v\right)>0$; moreover, it holds that $v\in B(a_{{\lambda }_v},2^{{\mathrm{\ell }}_{{\lambda }_v}-5})$, and thus $y_{{\mathrm{\ell }}_{{\lambda }_v}-4}(v,t_{{\lambda }_v})={(g_{v,{\mathrm{\ell }}_{{\lambda }_v}-4}(t_{{\lambda }_v}))}^{+}={(g_{v,{\mathrm{\ell }}_{\lambda }}(t_{{\lambda }_v}))}^{+}$. Thus, the counter $g_{v,{\mathrm{\ell }}_{\lambda }}$ has increased by at least $x_{\lambda }$ during the time interval $I_v:=(t_{\lambda },t_{{\lambda }_v}]$.

Next, we claim that inside $I_v$, there was no non-tertiary service ${\lambda }^{\prime }$ of level at least $\mathrm{\ell }$ such that $v\in B(a_{{\lambda }^{\prime }},2^{{\mathrm{\ell }}_{\lambda }})$. Assume otherwise, and note that ${\sigma }_{{\lambda }_v}$ is pending on $v$, and is of level exactly $\mathrm{\ell }$; thus, after ${\lambda }^{\prime }$, it would either be served or have ${\mu }_{{\sigma }_{{\lambda }_v}}$ be set to ${\lambda }^{\prime }$, in contradiction to ${\lambda }_v$ being assigned to $\lambda$.

As a result, we claim that every request on $v$ of level ${\mathrm{\ell }}_{\lambda }$ during $I_v$ belongs to $E_{\lambda }$. First, note that immediately after $\lambda$, all pending level-$\mathrm{\ell }$ requests on $v$ are in $E_{\lambda }$. Suppose for contradiction that this is broken at some point; that is, a new level-$\mathrm{\ell }$ request joins. This could only happen if its level is upgraded by some non-tertiary service during $I_v$, but there is no such service due to the previous claim.

Finally, note that the requests of $E_{\lambda }$ are pending in the optimal solution during $I_v$, as the optimal server did not visit $v$ during $I_{\mathrm{c}}(\lambda )$; thus, the optimal solution incurs the same delay cost of at least $x_{\lambda }$.

Assume that two triplets $(v,\mathrm{\ell },I_1)$, $(v,\mathrm{\ell },I_2)$ that are owned by services ${\lambda }_1,{\lambda }_2\in {\mathrm{\Lambda }}^{\text{c}}$, are such that $I_1\cap I_2\ne \mathrm{\varnothing }$; note that ${\mathrm{\ell }}_{{\lambda }_1}={\mathrm{\ell }}_{{\lambda }_2}=\mathrm{\ell }$. Assume without loss of generality that ${\lambda }_1$ is the earlier service; then, $t_{{\lambda }_2}\in I_1$. Note that $v\in B(a_{{\lambda }_2},2^{{\mathrm{\ell }}_{{\lambda }_2}})$; however, this cannot be, at no non-tertiary service $\lambda$ of level at least $\mathrm{\ell }$ can occur during $I_1$ such that $v\in B(a_{\lambda },2^{{\mathrm{\ell }}_{\lambda }})$, as seen in the proof of the first claim. $◀$

Consider the set of locations $W:={\mathrm{\Sigma }}_{\lambda }^{\circ }\setminus V_{\lambda }^{\ast }$, which is a subset of $V_{\lambda }$. These locations were not visited during $\lambda$, as the solution computed by PCSolve in Line 4 of Algorithm 2 does not include them. However, due to the guarantee of PCSolve in Lemma 4, this implies that

Noting that $W\subseteq B(a_{\lambda },2^{{\mathrm{\ell }}_{\lambda }})$, we have ${\mathrm{ST}}^{\ast }(W)\ge {\mathrm{ST}}^{\ast }(W;a_{\lambda })-2^{{\mathrm{\ell }}_{\lambda }}$. Applying Proposition 19, denoting by $G^{\ast }$ the subgraph traversed by OPT during $I_{\mathrm{c}}(\lambda )$, it holds that $c\left(G^{\ast }\cap B(a_{\lambda },3\cdot 2^{{\mathrm{\ell }}_{\lambda }})\right)\ge {\mathrm{ST}}^{\ast }(W)/2$. Combining the above, we get:

where the final inequality is due to the fact that $\left|{\mathrm{\Sigma }}_{\lambda }^{\circ }\right|=\lceil 2\sqrt{\left|V_{\lambda }\right|}\rceil$, due to Proposition 17. $◀$

The proof of Proposition 22 appears in Appendix B.

It holds that

where the first inequality is due to Proposition 21, and the second inequality is due to Proposition 22 and Proposition 20. $◀$