A QPTAS for Facility Location on Unit Disk Graphs

The goal of this section is to reduce Uncapacitated Facility Location in UDGs to more well-structured instances that, intuitively speaking, has the clients partitioned into annuli about facilities from some $\tilde{D}\subseteq F$ with bounded aspect ratio and that these facilities are near some facilities opened in an optimal solution. Definition 7 below contains the precise notion of what it means for an instance to be well structured. Corollary 9 is the main result from this section.

Given an instance $I=(G,C,F,f_i)$ of Facility Location, which consists of an edge-weighted graph $G$, a set of clients $C$, and a set of facilities $F$ with opening costs $f_i$ (for each $i\in F$), the first step of the algorithm in [8] involves partitioning the instance into separate (independent) sub-instances with specific structural properties. For any solution $D\subseteq F$, we denote by $\mathrm{conn}(D)$ the connection cost of $D$ (${\sum }_{c\in C}dist(c,D)$) and by $\mathrm{open}(D)$ the opening cost of facilities in $D$ (${\sum }_{i\in D}{f}_i$), and $\mathrm{cost}(D)=\mathrm{conn}(D)+\mathrm{open}(D)$. We sometimes use ${\mathrm{cost}}_I(D)$ to denote we refer to the cost of $D$ for instance $I$. To achieve this, they compute an $\alpha$-approximation solution $\tilde{D}$ (where $\alpha =O(1)$) to a modified instance $\tilde{I}=(G,C,F,ϵf_i)$ where each opening cost is scaled down by a factor of $ϵ$. In other words, $\tilde{D}$ is an $O(1)$-approximation for $\tilde{I}$. It is not hard to see that $\tilde{D}$ is also an $O(1/ϵ)$-approximation for $I$. For any $i\in \tilde{D}$, let $cluster(i)$ denote the set of clients connected to $i$ in this solution and define $avgcost(i)=\frac{f_i+{\sum }_{j\in cluster(i)}{d}_G(j,i)}{|cluster(i)|}$ be the average cost of the cluster by facility $i$. Suppose $D^{\ast }$ is the set of facilities in an optimum solution to $I$. So the cost of $(\tilde{D})$ is at most $\frac{1}{ϵ}$ times cost of $D^{\ast }$. They show:

Then they build a modified instance $I^{\prime }=(G,C^{\prime },F,f_i)$ where clients of each $cluster(f)$ are not too close or too far away from $f$ compared to $avgcost(f)$. Let ${\mathrm{opt}}^{\prime }$ be the cost of an optimum solution to $I^{\prime }$ and $\mathrm{opt}$ be the cost of an optimum solution to $I$. They show that:

Therefore, a near optimum solution to $I^{\prime }$ yields a near optimum solution to $I$. In order to be able to obtain a PTAS they further partition the instance (starting from $I$) into several instances $I_j$ each of which has certain structural properties.

They show that one can partition $I$ into instances $I_j=(G,C_j,F_j,f_i^j)$ such that each instance satisfies the structural properties of Definition 7 and also how to combine solutions for the various $I_j$ to get a good solution for $I^{\prime }$:

Recall that all these results only use the metric property of instance $I$. The preceding lemmas show that to prove Theorem 1 it is sufficient to present a QPTAS for instances satisfying conditions of Definition 7 and this is what we will do. We state this formally.

In order to get a PTAS for well-structured instances in the planar case, [8] uses a Baker-type type layering technique [3] in conjunction with the properties of the instance, and further decompose the instance into instances of constant radius at a small loss. By utilizing balanced separators for planar graphs, they obtain a hierarchical decomposition of the plane embedding of the graph into separate regions (similar to the decomposition of Euclidean instances by Arora [2]). By placing $O(\log n)$ “portals” along each separator they use dynamic programming over this decomposition, while the portals control the interface of different regions.

In our setting, instead of using Baker layering to obtain low diameter instances, we use Theorem 3 to break the instance that satisfies conditions of Definition 7 (at a small loss) into low diameter instances. We will use a variant of a balanced separator theorem developed by [12] (which improved over a more complex separator by [27]) for UDGs. Roughly speaking, they show that given a UDG, one can find two paths originating from a vertex $s$ to two other vertices $x,y$ that are shortest paths, $P_{s\sim x}$ and $P_{s\sim y}$, such that the removal of these two paths and all the vertices that are within distance 1 of them leaves connected components of size at most $\frac{2}{3}|V(G)|$ (see Theorem 10). We adapt this theorem to get an (almost) balanced separator to obtain a hierarchical decomposition of a low diameter instance into smaller instances. We also place $O(\log n)$ portals at these separators and use Dynamic Programming to combine the solutions. After a logarithmic depth of hierarchical decomposition, we arrive at instances that are easy to solve using other methods (e.g. another PTAS that is described in Theorem 4).

To obtain our dynamic program scheme, we would like to be able to break a UDG into (almost) balanced parts by picking a separator. This will act as a “cut” in the disection schema developed by Arora [2] that has been used in designing PTAS’s for various optimization problems on Euclidean plane. For this, we utilize the balanced separator theorem for UDGs as presented by Yan et al. [12]. Let $N_G^i[v]=\{u\in V(G):d_G(v,u)\le i\}$ and $N_G^i[S]={\cup }_{v\in S}{N}_G^i[v]$. A hop-shortest path between two nodes $x,y$ is a path with the minimum number of edges.

Theorem 13 in [12] actually only proves it for the case $X=V$. See Appendix A for discussion about why it holds for general $X\subseteq V$. This theorem serves as a counterpart to the well-known balanced shortest paths separator theorem in planar graphs by Lipton and Tarjan. However, it poses a challenge due to the fact that the separator is formed by the 1-neighborhoods of the paths rather than just the paths themselves. This means that we must not only remove the shortest paths but also all nodes within a distance of one from the nodes on the shortest paths. To tackle this challenge, we narrow our focus to cases where the average distance between clients and facilities is relatively large. By doing so, we can assume that clients and facilities, which end up on two different sides of the shortest path, always get connected via nodes in $V(P_{s\sim x}\cup P_{s\sim y})$. Note that, as stated in Theorem 11 (which is a slight modification of this theorem), the only exceptions to this assumption occur when the path between clients and facilities crosses the border using an edge whose endpoints are very close to nodes in $V(P_{s\sim x}\cup P_{s\sim y})$. However, using the fact that we can assume the average distance between clients and facilities is relatively large, we can force those paths to visit nodes in $V(P_{s\sim x}\cup P_{s\sim y})$ with a relatively tiny error.

In the following, we demonstrate that a slight modification of this theorem yields a balanced, yet partial in some sense, separator for UDGs. More precisely:

This follows easily from Theorem 10 but we provide a proof in Appendix A for the sake of completeness. Note that we say $V(P_{s\sim x}\cup P_{s\sim y})$ is a separator between $V(G_1)$ and $(G_2)$ if there are no edges in $G$ that connect a vertex from set $V(G_1)$ to a vertex from set $V(G_2)$. However, here, we relax this condition and allow for the presence of such edges, provided that their endpoints are in close vicinity to the separator.

Let $\mathrm{\Gamma }=3rN/{ϵ}^2=O_{ϵ}(N)$ denote the diameter of the graph. Our goal is to obtain a net of size $\mathrm{poly}(\mathrm{\Gamma })$ so that the number of points we deal with is in terms of $N$ (instead of $n$), while we loose a small factor (compared to $\mathrm{opt}$).

We can think of $B(v)$ as the set of nodes in a ball of radius $1/8$ around $v$. The proof is by a fairly standard net construction and is found in Appendix A. Note that the error described above when summed over all $H_{\mathrm{\ell }}$’s, is at most $O(|C|)=O(\mathrm{cost}(\tilde{D})/N)=O(ϵ\cdot \mathrm{opt})$ (since $N|C|\le \mathrm{cost}(\tilde{D})$).

We obtain a hierarchical decomposition of $G^{\prime }$ which will be associated with a rooted binary tree $T$ where the root of $T$ is $V^{\prime }$. We will have a Dynamic Programming to solve Facility Location using this decomposition. This will be similar to the hierarchical decompositions obtained for PTAS’s on the Euclidean instances (e.g. [2]) except that we use the separator in Theorem 11 instead of dissecting lines and that the leaf nodes in our decomposition tree in our case do not correspond to trivial instances (typically a leaf node is a box with only one point in it). In our case, each leaf node is an instance with certain properties which enables us to solve it in quasi-polynomial time at a small loss.

Let us describe the decomposition for $G^{\prime }$. Our hierarchical decomposition tree $T$ is associated with a labeling $\psi :V(T)\to 2^{V(G^{\prime })}$: we set the label of the root of $T$ to be $V(G^{\prime })$. Each $t\in T$ represents a subgraph $G^{\prime }[\psi (t)]$ with the property that if $t_1,t_2$ are children of $t$, then $\psi (t)=\psi (t_1)\cup \psi (t_2)$. We use $\text{bd}(t)$ to denote the boundary vertices of $\psi (t)$ and the rest of the vertices, $\psi (t)-\text{bd}(t)$, we call them the core vertices and are denoted by $X(t)$. The “boundary” is obtained by finding a separator using Theorem 11 and is added to the boundary that is inherited from the parent (details to follow). The boundary of the root node is the empty set (and so all the vertices of $G^{\prime }$ are core vertices for the root node of $T$). The overall idea is whenever a current leaf node $t\in T$ has $|X(t)|>1$ we decompose $G^{\prime }[\psi (t)]$ into two smaller subgraphs and we obtain children $t_1,t_2$ for $t$. More specifically, starting from when $T$ is a single node $t$ corresponding to $V(G^{\prime })$, iteratively, for each leaf $t$ of $T$, if $|X(t)|>1$, apply Theorem 11 over $G^{\prime }[\psi (t)]$ with $X=X(t)$ to obtain two graphs $G_1^{\prime }$ and $G_2^{\prime }$, along with the two shortest paths $P_{s\sim x}$ and $P_{s\sim y}$. We use the same vertex $s$ to find the two shortest paths $P_{s\sim x},P_{s\sim y}$ for each node $t\in T$ and we make sure this vertex $s$ is passed down. Define $\psi (t_i)$ to be $G[V(G_i^{\prime })\cup V(P_{s\sim x})\cup V(P_{s\sim y})]$ and $\text{bd}(t_i)=\text{bd}(t)\cup P_{s\sim x}\cup P_{s\sim y}$. This also defines $X(t_i)$ to be the subset of vertices of $X(t)$ that fall into $V(G_i^{\prime })$ and not in the boundary of $t_i$. Note that our separator $P_{s\sim x}\cup P_{s\sim y}$ separates the vertices $\psi (t)$ of our sub-instance into parts each of which has at most $\frac{2}{3}|X(t)|$ many core vertices.

Every time we find a separator $P_{s\sim x}\cup P_{s\sim y}$ to break the graph $\psi (t)$ (as described) we also designate $m=O_{ϵ}(\log N)$ of the vertices of each of these two paths as portals. More specifically, let $\delta =O(ϵ\mathrm{\Gamma }/\log N)$ and designate some of the vertices of these paths as portal so that they are $\delta$ apart (note that as mentioned before, the hop-distance and UDG distances are within factor 2 of each other). Since these paths have hop-distance length at most $\mathrm{\Gamma }$, we will have $O_{ϵ}(\log N)$ portals per path. Our intention is that if two points $u\in X(t_1)$ and $v\in X(t_2)$ are to be connected they have to go through portals of the boundary. This is illustrated in Figure 1.

Observe that the depth of $T$ is $h=O(\log \mathrm{\Gamma })=O_{ϵ}(\log N)$ (recall that $|V(G^{\prime })|=O({\mathrm{\Gamma }}^4)$). By construction, for each node $t\in T$, the region defined by $\psi (t)$ consists of core nodes in $X(t)$ and the boundary $\text{bd}(t)$ consists of (at most) $h$ separators (which are shortest paths starting from $s$) obtained using Theorem 11 each of length proportional to the diameter of the graph, namely $\mathrm{\Gamma }$. For any $t$ let ${\mathrm{\Pi }}_t$ be the set of portals on the boundary of region $t$. Note that each region boundary is composed of at most $h=O_{ϵ}(\log N)$ paths and each path has $O_{ϵ}(\log N)$ portals, so each $t$ has at most $O_{ϵ}({\log }^{2}N)$ portals.

By Theorem 11 and the way we put the portals (since they are $\delta$ apart), it follows that for any two points $u^{\prime }\in \psi (t_1)$ and $v^{\prime }\in \psi (t_2)$ (where $t_1,t_2$ are children of a node $t\in T$), there exists a portal $\pi$ in the separator that breaks $t$ into $t_1,t_2$ for which $d_{G^{\prime }}(u^{\prime },\pi )+d_{G^{\prime }}(v^{\prime },\pi )\le d_{G^{\prime }}(u^{\prime },v^{\prime })+\delta +4$. Now if $u\in B(u^{\prime }),v\in B(v^{\prime })$ are two vertices of $H_{\mathrm{\ell }}$ (recall that $B(v^{\prime })$ is the ball of $v^{\prime }$ that created net node $v^{\prime }$ in $G^{\prime }$), the distance between $u,v$ to go via their ball centers and then via the portal is bounded as well: $d_G(u,u^{\prime })+d_{G^{\prime }}(u^{\prime },\pi )+d_{G^{\prime }}(v^{\prime },\pi )+d_G(v,v^{\prime })\le d_{G^{\prime }}(u^{\prime },v^{\prime })+\delta +4.25\le d_G(u,v)+\delta +5$.

Suppose we require, for each node $t\in T$ with children $t_1,t_2$, the connection between points in $\psi (t_1),\psi (t_2)$ be via portals in the separator that broke $t$ into $t_1,t_2$. As argued above, this detour adds at most $\delta +5$ to the cost for each connection. Since the depth of the recursion tree $T$ is $h=O(\log \mathrm{\Gamma })$, the accumulated error incurred to each client/facility for communicating via portals and centers of their balls (among all the levels of the decomposition) is at most $O((\delta +5)\log \mathrm{\Gamma })$. Hence, there is a total error of at most $O(|C_{\mathrm{\ell }}|\delta \log \mathrm{\Gamma })$ for all clients connections. By a suitable choice of ${ϵ}^{\prime }$ depending on $ϵ$, and setting $\delta =\frac{{ϵ}^{\prime }\mathrm{\Gamma }}{\log \mathrm{\Gamma }}$, we get $m=\frac{\log \mathrm{\Gamma }}{{ϵ}^{\prime }}=\frac{\log O_{ϵ}(N)}{{ϵ}^{\prime }}$, the total error for re-routing connections of clients to be via portals (among all levels of decomposition) between regions is bounded by:

This will be our additive error $E_{\mathrm{\ell }}$. Recall that we have $N\cdot |C|\le O(\mathrm{opt}/ϵ)$, implying $|C|\le O(\frac{\mathrm{opt}}{ϵN})$. This, together with (1) and the fact that ${\sum }_{\mathrm{\ell }}|C_{\mathrm{\ell }}|\le |C|$, imply that the total additive error for all $H_{\mathrm{\ell }}$’s is bounded by $O(ϵ\cdot \mathrm{opt})$ if ${ϵ}^{\prime }$ is sufficiently small.

Consider an arbitrary node $t\in T$ and portals ${\pi }_1,\mathrm{\dots },{\pi }_{m^{\prime }}$ (where $m^{\prime }=O_{ϵ}({\log }^{2}N))$ on the paths that define $\text{bd}(t)$. For each portal ${\pi }_i$ we will have two values $in({\pi }_i),out({\pi }_i)$: $in({\pi }_i)$ indicates (approximately) the distance to the nearest facility (to ${\pi }_i$) that is supposed to be open in the instance defined by $\psi (t)$, and $out({\pi }_i)$ indicates (approximately) the distance to the nearest facility (to ${\pi }_i$) that will be open outside the region defined by $\psi (t)$ (and clients inside the balls of vertices of $\psi (t)$ can be connected to them via ${\pi }_i$ by paying an additional distance cost of $out({\pi }_i)$). These distances are “approximate” since we only keep multiples of $\delta$, since having a precision parameter of $\delta$ (as argued above) results in total error $O(ϵ\cdot \mathrm{opt})$.

For any $t\in T$ and any two vectors $\overrightarrow{in},\overrightarrow{out}$ of dimensions $m^{\prime }$ (for the portals of $t$) we will have a DP table entry $A[t,\overrightarrow{in},\overrightarrow{out}]$. This entry is supposed to store the (approximate) cost of an optimum solution to the Facility Location instance defined by the balls $B(\psi (t))$ (where $B(S)={\cup }_{v\in S}B(v)$) subject to the following conditions:

• $\mathrm{■}$

  for each portal ${\pi }_i$ there is an open facility in the solution with distance to ${\pi }_i$ at most as specified by $in({\pi }_i)$,

• $\mathrm{■}$

  for each client either it is served by an open facility inside, or is paying connection cost to go to a portal ${\pi }_i$ and if $n({\pi }_i)$ is the number of clients that go to portal ${\pi }_i$ then they pay $n({\pi }_i)\times out({\pi }_i)$ to get serviced by a facility outside of $\psi (t)$ at distance $out({\pi }_i)$. This will be part of the cost for the solution.

We say vector $\overrightarrow{in}$ (and similarly $\overrightarrow{out}$) is valid if it satisfies the following condition: for any two portals $\pi ,{\pi }^{\prime }$, if their distance (rounded to the nearest multiple of $\delta$) is $z$ then $|in(\pi )-in({\pi }^{\prime })|\le z+\delta$. This condition clearly must hold as if there is a facility with distance $in(\pi )$ from $\pi$ then the nearest facility to ${\pi }^{\prime }$ cannot be further than $\in (\pi )+z+\delta$ away from it. Our DP table is computed only for valid vectors for each node $t\in T$.

Suppose we have computed (approximate) solutions for each problem defined for each leaf node of $T$ and each (valid) vectors $\overrightarrow{in},\overrightarrow{out}$ for the portals. Our DP will compute the solution for the instance of root of $T$ (i.e. $V(G^{\prime })$) in a bottom up manner from the leaf nodes to the root. For each internal node $t$ with children $t_1,t_2$ and vectors $\overrightarrow{in},\overrightarrow{out}$ (for $t$) and ${\overrightarrow{in}}_1,{\overrightarrow{out}}_2,{\overrightarrow{in}}_2,{\overrightarrow{out}}_2$ (for $t_1,t_2$, respectively) it will see if the three solutions are “consistent”. We will define this formally in the next section but at a high level this checks whether the solutions for $t_1,t_2$ (given the portal vectors) can be combined so that we get a solution for $\psi (t_1)\cup \psi (t_2)$ where it is consistent with the vectors of portals specified by $t$.

If one keeps the distances (stored in portal vectors) as as multiples of $\delta$, since distances are bounded by $\mathrm{\Gamma }=O_{ϵ}(N)$, there will be $O_{ϵ}(\log N)$ choices for each portal, which leads to a ${(\log N)}^{O_{ϵ}({\log }^{2}N)}$ table size.²²2We can reduce this using a trick that is also used earlier (e.g. see [2]) to show how to reduce the size of the portal vectors by storing only “smoothed” vectors. Informally, the observation that helps is that if we keep distances of the nearest facility (inside or outside) for a portal ${\pi }_i$ as the multiple of $\delta$ then if the value for portal ${\pi }_i$ is $\sigma$ then the value for portal just before or after ${\pi }_i$ on the separator path that ${\pi }_i$ belongs to is in $\{\sigma -1,\sigma ,\sigma +1\}$. Thus, the total number of vectors we need to consider for a node $t\in T$ is $O_{ϵ}({\log }^{2}N\times 3^{m^{\prime }})=2^{O_{ϵ}({\log }^{2}N)}$, where there are $O_{ϵ}({\log }^{2}N)$ choices for the first portal values and then for the subsequent portals there are only $3$ choices for each distance. The base case will be solved using an exhaustive search by guessing a subset of portals and opening the cheapest facility on that portal followed by a check if the distance requirements for facilities are satisfied: the best consistent solution will be kept and we will store $\mathrm{\infty }$ if there is no such solution.

We first show the existence of a near optimum solution with certain properties such that our DP actually finds such a near optimum solution. Starting from an optimum solution $D_{\mathrm{\ell }}^{\ast }$ on $H_{\mathrm{\ell }}$ we make some changes to it to satisfy the properties we want, while increasing the cost a little only. First for each node $v\in V^{\prime }$ with $D_{\mathrm{\ell }}^{\ast }\cap B(v)\ne \mathrm{\varnothing }$ we consider keeping the cheapest open facility in $B(v)$ and closing all the others and re-routing all the clients that were served by other facilities in $B(v)$ to that single open facility via $v$. This adds at most $1/4$ to the distance each client has to travel (via $v$) as nodes in $B(v)$ have distance at most $1/8$ to $v$. This increases the cost by at most $O(|C_{\mathrm{\ell }}|)$ over all clients. We can assume the open facilities are on the centers of the balls now. Let’s call this new (near optimum) solution $D_{\mathrm{\ell }}^{\prime }$. Next we modify the solution further by the following process. We say a solution is $t$-adapted for a node $t\in T$ if (i) for each of its descendant $t^{\prime }$ the solution is $t^{\prime }$-adapted, and (ii) for each client $c\in B(\psi (t))$, if $c$ is connected to a facility outside of $B(\psi (t))$ then it is connected via a portal $\pi \in \mathrm{\Pi }$, where $\mathrm{\Pi }$ is the set of portals of $t$.

We start with $D_{\mathrm{\ell }}^{\prime }$ and at leaf nodes of $T$ and going up the tree, we make the solution $t$-adapted for each $t\in T$ at small increase in cost. Let us consider a leaf node $t\in T$ with $X(t)=w_t$ (the case when $X(t)=\mathrm{\varnothing }$ is even easier) and boundary $\text{bd}(t)$ corresponds to paths with a total of $m^{\prime }$ portals $\mathrm{\Pi }={\pi }_1,\mathrm{\dots },{\pi }_{m^{\prime }}$. We consider $w_t$ as a portal as well and add it to $\mathrm{\Pi }$. Suppose ${\mathrm{\Pi }}^{\prime }={\pi }_{a_1},{\pi }_{a_2},\mathrm{\dots },{\pi }_{a_{\sigma }}$ is the subset of $\mathrm{\Pi }$, where there is a facility in distance at most $\delta$ of ${\pi }_{a_i}$ in $D^{\prime }\cap \psi (t)$. For each such ${\pi }_{a_i}$, we assume we have kept open the cheapest facility within $\delta$ of it. For any client $c\in B(\psi (t))$ if $c$ was connected to a facility in $B(\psi (t))$ in $D^{\prime }$ (note that all of those are within distance $\delta$ of some portal in ${\mathrm{\Pi }}^{\prime }$) we consider routing $c$ to the nearest portal in ${\mathrm{\Pi }}^{\prime }$ (and then from there to the single cheap facility we kept open). Note that this increases the connection cost for each client by at most $2\delta$. If $c$ was connected to a facility outside of $B(\psi (t))$ we re-route it first to a nearest portal $\pi$ along its way and then from there to be connected to the facility it was connected to outside of $B(\psi (t))$ (i.e. we make the connection of $c$ to go through a portal). This increases the connection cost for each $c$ by at most $\delta +5$ as argued earlier in the overview and the solution becomes $t$-adapted.

Now suppose $t\in T$ is a non-leaf node with children $t_1,t_2$ and supposed $D_{\mathrm{\ell }}^{\prime }$ is $t_1$-adapted and $t_2$-adapted. We make it $t$-adapted with small increase in the cost. For any client $c\in B(\psi (t))$, if $c$ is connected to a facility in $\psi (t)$ we don’t need to make any further changes. Otherwise we make a detour for the connection of $c$ to go through one of the portals $\mathrm{\Pi }$. This detour increases the connection cost of a client by at most $2\delta$.

One last change we do is in the calculation of the cost of the adapted solution to make it portal vector adapted: for each node $t\in T$, the $t$-adapted solution also induces vectors $\widetilde{in},\widetilde{out}$ for portals of $t$ in the following way. The clients that are served by facilities outside $\psi (t)$ are first going to a portal $\pi$ (of $t$). The distance from that portal to the nearest open facility (outside $\psi (t)$) rounded up to the nearest multiple of $\delta$ is what induces a value for $\widetilde{out}(\pi )$ at node $t$. We use this rounded (up) value instead of the actual distance in the calculation of the cost of the $t$-adapted solution. Similarly, for each portal $\pi$, the distance to the nearest open facility in $\psi (t)$ rounded to the nearest multiple of $\delta$ induces a value $\widetilde{in}(\pi )$ for node $t$. Let $\widetilde{in},\widetilde{out}$ correspond to the vectors induced by the $t$-adapted optimum solution. We assume the cost a client pays to go out of $\psi (t)$ to be connected to a facility via a portal $\pi$ (from $\pi$) is $\widetilde{out}(\pi )$. Note that our estimate of the nearest to $\pi$ open facility inside or outside $\psi (t)$, described by $\widetilde{in}(\pi ),\widetilde{out}(\pi )$ has an additive error of at most $\delta$. Thus, the connection costs for each client at each node $t$ can be larger by $\delta$ again. We call this new cost, portal vector adapted.

It is easy to see that if we make the solution $t_0$-adapted, where $t_0$ is the root of $T$, and consider the portal adapted cost (as described), then the increase in the connection cost for each client over all the nodes of $T$ is at most $O(\delta \log \mathrm{\Gamma })$ (since the height of $T$ is $O(\log \mathrm{\Gamma })$); summed over all the clients this was shown to be $O({ϵ}^{\prime }|C_{\mathrm{\ell }}|\mathrm{\Gamma })$. Thus, the best $t_0$-adapted and portal adapted solution has cost $\mathrm{opt}({\mathrm{H}}_{\mathrm{\ell }})+\mathrm{O}({ϵ}^{\prime }|{\mathrm{C}}_{\mathrm{\ell }}|\mathrm{\Gamma })$, and for a suitable choice of ${ϵ}^{\prime }$ the additive error over all $H_{\mathrm{\ell }}$’s will be add to at most $O(ϵ\cdot \mathrm{opt})$.

Let $\widetilde{in},\widetilde{out}$ correspond to the vectors induced by the $t_0$-adapted near optimum solution. By this argument it is enough to find compute the entries $A[t_0,\overrightarrow{0},\overrightarrow{0}]$ to obtain a $(1+O(ϵ))$-approximate solution.