Directed Buy-At-Bulk Spanners

Previous work [12, 17, 5, 40] reduces the buy-at-bulk problem to the two-metric network design problem, with only a constant factor loss in the approximation guarantee.

In this problem, each edge $e\in E$ has a one-time setup cost $\sigma (e)$ and a maintenance cost $\delta (e)$ ⁴⁴4Previous literature uses the term length to refer to $\delta (e)$. In our case, $\delta (e)$ does not capture any local constraints; it can only handle a global objective. In the context of say the internet, $\delta (e)$ would be the maintenance cost of the internet due to the load; not the latency of individual users.. The objective is to minimize the cost

We note that adding distance constraints does not affect the reduction. Let $𝒟\subseteq ℝ$ be the domain for the length of each edge. We consider the following problem throughout the paper with different options of $𝒟$.

The performance of an approximation algorithm is measured by the approximation ratio, the ratio between the cost of the approximate solution and that of the optimal solution.

For Buy-at-bulk Spanner, we consider two domains for edge lengths, $𝒟={[\mathrm{𝗉𝗈𝗅𝗒}(n)]}_{\pm }:=\{j\in \mathbb{Z}\mid |j|\le \mathrm{𝗉𝗈𝗅𝗒}(n)\}$ and $𝒟=ℝ$. When the problem has unit demands, Buy-at-bulk Spanner is termed Unit-demand Buy-at-bulk Spanner. In a special case of Buy-at-bulk Spanner where the source vertex $s\in V$ is fixed, we call this problem Single-source Buy-at-bulk Spanner. For notation convenience, we have $D\subseteq \{s\}\times V$. We say that $s$ is the root vertex. The definition for a single-sink buy-at-bulk spanner where the terminal pairs share the same sink is defined similarly.

In the online buy-at-bulk spanner problem, each terminal pair and its corresponding demand and budget arrive in an online fashion, one at a time. The other parts of the input, including the graph, edge costs, and edge lengths, are provided in advance. The goal is to irrevocably select a path to satisfy the terminal demand pair within the distance budget. We add the prefix Online to the problem of interest to denote the online version of that problem. The vertex pair $(s_i,t_i)$ denotes the $i$-th pair that arrives online.

In Section 2, we prove the following for Unit-demand Buy-at-bulk Spanner on ${[\mathrm{𝗉𝗈𝗅𝗒}(n)]}_{\pm }$.

Theorem 3 generalizes the $\tilde{O}(n^{4/5+\epsilon })$-approximation algorithm for the unit-demand directed buy-at-bulk network design problem [5] and directed weighted spanners [32], by allowing distance constraints.

Next, we turn to online buy-at-bulk spanners. The performance of an online algorithm is measured by its competitive ratio, that is, the ratio between the cost of the online solution and that of an optimal offline solution. With non-unit demand, we show the following.

Corollary 4 generalizes the $\tilde{O}(k^{1/2+\epsilon })$-competitive algorithm for directed weighted spanners [32] and buy-at-bulk network design [5, 12], and the $\tilde{O}(k^{\epsilon })$-competitive algorithm for the single-source version of these problems, by allowing general demands, pay-per-use cost, and distance constraints.

Without distance constraints, Online Buy-at-bulk Spanner captures the online buy-at-bulk problem. Set the distance of each edge to one and the distance budget of each terminal pair to $n$. The state-of-the-art results are $\tilde{O}(k^{1/2+\epsilon }\log R)$-competitive for online buy-at-bulk and $\tilde{O}(k^{\epsilon }\log R)$-competitive for online single-source buy-at-bulk. Here, $R$ is the ratio between the maximum and minimum demand [12]. We show the following result for Online Buy-at-bulk Spanner and Online Single-source Buy-at-bulk Spanner on ${[\mathrm{𝗉𝗈𝗅𝗒}(n)]}_{\pm }$, which removes the dependency of $R$ from the competitive ratio in the result of [12]. Note that $R$ is independent of $n$ or $k$ and in practice could be very large.

Next, we consider Online Buy-at-bulk Spanner on $ℝ$ by slightly relaxing the distance constraints. This also allows us to obtain approximation algorithms for Online Buy-at-bulk Spanner on ${[\mathrm{𝗉𝗈𝗅𝗒}(n)]}_{\pm }$ in terms of $k$ (Corollary 4). For notation convenience, we define some condition numbers. Let

Intuitively, $\eta$ denotes the ratio between the magnitude of the most negative edge length and the smallest absolute value of the budget.⁷⁷7$\eta$ cares about ${\min }_{e\in E}\{{\mathrm{\ell }}_e\}$, but not about ${\max }_{e\in E}\{{\mathrm{\ell }}_e\}$. This is because we can safely ignore edges that are much longer than the budget, but we cannot do so for edges (with negative lengths) that are much shorter than the budget. If edge lengths are all non-negative, then $\eta =0$. Similarly, $\xi$ denotes the ratio between the largest and the smallest absolute value of the budget. To accommodate a negative distance budget, we use the $\mathrm{sgn}$ function

For Online Buy-at-bulk Spanner on $ℝ$, we assume that the condition numbers $\eta$ and $\xi$ are given in advance. This is not necessary for the offline version of this problem or for the Online Buy-at-bulk Spanner on ${[\mathrm{𝗉𝗈𝗅𝗒}(n)]}_{\pm }$ .

Suppose we are given a tolerance parameter $\theta >0$. When the distance budget is positive, the goal is to satisfy the distance constraint within a factor of $(1+\theta )$. When the distance budget is negative, the distance between the terminal pair is below $(1-\theta )$ times the budget. We prove Theorem 6 in the full version paper [33].

When the edge lengths are non-negative, $\eta =0$, so the running time is $\mathrm{𝗉𝗈𝗅𝗒}(n,1/\theta ,\xi )$.

When the domain $𝒟={[\mathrm{𝗉𝗈𝗅𝗒}(n)]}_{\pm }$, observe that it is sufficient to consider that $\text{Dis}(s,t)\in \mathrm{𝗉𝗈𝗅𝗒}(n)$. This in turn guarantees a $\mathrm{𝗉𝗈𝗅𝗒}(n)$ upper bound for $\xi$ and $\eta$. This upper bound can be obtained by processing the input graph (even when we don’t know the distance constraints) and therefore for Online Buy-at-bulk Spanner on ${[\mathrm{𝗉𝗈𝗅𝗒}(n)]}_{\pm }$, we don’t need to know the condition numbers in advance. From Theorem 6, when the domain $𝒟={[\mathrm{𝗉𝗈𝗅𝗒}(n)]}_{\pm }$, we can set $\theta =1/\mathrm{𝗉𝗈𝗅𝗒}(n)$ (based on the upper bounds of $\xi$ and $\eta$) such that the distance constraints are satisfied. This implies Corollary 4.

In one special case of Online Buy-at-bulk Spanner where for all edges, the upfront cost is one, the maintenance cost is zero, and the lengths are positive, the problem is termed Online Pairwise Spanner. Theorem 6 and Corollary 4 imply Corollaries 8 and 9, respectively, using the following lemma.

Corollary 8 is comparable with the $\tilde{O}(n^{4/5+\epsilon })$-competitive result for Online Pairwise Spanner and the $\tilde{O}(n^{2/3+\epsilon })$-competitive result for Online Pairwise Spanner with unit edge lengths [34]. The improvement in the competitive ratio and the domain of the edge lengths has a trade-off of slightly violating the distance constraints. Corollary 9 generalizes the result for Online Pairwise Spanner from unit edge lengths to edge lengths in $[\mathrm{𝗉𝗈𝗅𝗒}(n)]$.

We emphasize again that Buy-at-bulk Spanner unifies the buy-at-bulk network design and spanners problems. Our results expand the domain for some results in the existing literature on these two problems. We allow edge lengths to be negative and of arbitrary magnitude (provided they are well-conditioned). There are no directed spanner results that account for edge lengths with negative values and arbitrary magnitude that we are aware of.

In previous literature, one main engine for solving the directed pairwise spanner problem [18, 34], the directed buy-at-bulk network design problem [56, 12, 17, 5], and the directed Steiner forest problem [9, 13, 28, 16] is the notion of junction tree. The notion of junction tree used for these problems is a union of an in-arborescence and an out-arborescence both rooted at the same vertex. For our purpose, we extend the definition of junction trees to handle both buy-at-bulk costs and distance constraints.

To further extend our results to the domain $ℝ$ for edge lengths, we define and use a relaxed version of distance-constrained junction trees. This allows us to obtain approximation algorithms for ($\theta$-relaxed) Minimum-density Distance-constrained Junction Tree (Theorem 12 and Corollary 13) later on.

The crucial subproblem for solving Buy-at-bulk Spanner on $ℝ$ is defined as follows.

When the edge lengths are non-negative, $\eta =0$, so the running time is $\mathrm{𝗉𝗈𝗅𝗒}(n,1/\theta ,\xi )$.

When the domain $𝒟={[\mathrm{𝗉𝗈𝗅𝗒}(n)]}_{\pm }$ and it is required to exactly satisfy the distance constraints, the problem $\theta$-relaxed Minimum-density Distance-constrained Junction Tree is termed Minimum-density Distance-constrained Junction Tree. From Theorem 12, we can set $\theta =1/\mathrm{𝗉𝗈𝗅𝗒}(n)$ (for a sufficiently large $\mathrm{𝗉𝗈𝗅𝗒}(n)$) such that the distance constraints are satisfied and the condition numbers $\eta$ and $\xi$ are polynomial in $n$ (since it is sufficient to consider that $\text{Dis}(s,t)\in \mathrm{𝗉𝗈𝗅𝗒}(n)$). This implies the following.

Corollary 13 generalizes the minimum density junction tree used for buy-at-bulk network design [5], pairwise spanners [18], and weighted spanners [32], with the same approximation ratio. We emphasize that our minimum-density junction tree framework accounts for buy-at-bulk costs and distance constraints with negative edge lengths. Furthermore, since junction trees and their variants are used in several algorithms in network design, we believe Theorem 12 and Corollary 13 which extend the junction tree black box in multiple ways are of independent interest. For instance, Corollaries 8 and 9 which improve existing results for Online Pairwise Spanner are obtained by simple application of our improved blackbox. An interesting question to ask is if Theorem 12 can be used in the same way to extend other such results (see for instance [18]).

In previous literature, one crucial case analysis for solving directed spanner problems [21, 9, 18, 34, 32] and the directed buy-at-bulk network design problem [5] is via flow-based linear programs (LP). The LP formulations for spanners potentially contain an exponential number of constraints and thus require an efficient black-box subroutine to be solved in polynomial time. A fully polynomial time approximation scheme (FPTAS) for the restricted shortest path problem [43, 47] is treated as an approximate separation oracle to approximately solve the flow-based LP for spanners.

We design and use an approximation scheme for the resource-constrained shortest paths problem with negative resource consumption, a generalization of the FPTAS for the restricted shortest path problem [44] in order to further accommodate buy-at-bulk costs for spanners with negative edge lengths. We believe this generalization is of independent interest since it can be used to extend the results which use [47, 43, 44].

We note that when $m=1$ and the resource consumption is non-negative, $m$-RCSP captures the restricted shortest path problem. In the LP for Buy-at-bulk Spanner, the constraints can be captured by solving $m$-RCSP. For $m$-RCSP, we design an algorithm that finds an optimal solution that slightly violates the resource budget.

Let ${\text{OPT}}_{RCSP}$ be the cost of any minimum cost $s\mathrm{⤳}t$ path that satisfies the resource constraints. Given a tolerance vector $({\epsilon }_1,{\epsilon }_2\mathrm{\dots },{\epsilon }_m)\in {ℝ}_{>0}^m$, a $(1;1+{\epsilon }_1,1+{\epsilon }_2\mathrm{\dots },1+{\epsilon }_m)$-approximation scheme finds a $𝓔$-multicriteria-feasible (see definition 15) $s\mathrm{⤳}t$ path whose cost is at most ${\text{OPT}}_{RCSP}$. Let the condition number

denote the ratio between the magnitude of the most negative $i$-th resource consumption among the edges and the absolute value of the budget for the $i$-th resource.

When $w_i(e)>0\forall i\in [m],e\in E$, Theorem 16 directly recovers the FPTAS from [44].

We summarize our main results for Buy-at-bulk Spanner in Table 1 by listing the approximation ratios and contrasting them with the corresponding known approximation ratios. The running time for Buy-at-bulk Spanner and Single-source Buy-at-bulk Spanner on ${[\mathrm{𝗉𝗈𝗅𝗒}(n)]}_{\pm }$ is polynomial. The running time for the $\theta$-feasible or relaxed results on $ℝ$ is $\mathrm{𝗉𝗈𝗅𝗒}(1/\theta ,\eta ,\xi ,n)$ ($\mathrm{𝗉𝗈𝗅𝗒}(n,1/\theta ,\xi ,\log \left({\max }_{e\in E}\{|{\mathrm{\ell }}_e|\}\right))$ for Online Pairwise Spanner).

We now sketch the proof of Theorem 12. This is our main technical result and an important tool for deriving many of our other results, i.e., Theorems 3 and Corollary 8.

At a high level, junction trees form a cheap partial solution that connects a subset of terminal pairs. For Buy-at-bulk Spanner, a potential approach is to iteratively select a low-density junction tree in case there exist edges that are crucial for connecting terminal pairs. For our purpose, we have to construct feasible junction trees that satisfy the distance constraints while connecting terminal pairs. The modified junction-tree-based approach is the main engine of our framework.

Suppose we have a fixed root vertex $r\in V$, and the goal is to find a minimum-density junction tree rooted at $r$. Here, the density is defined as the cost of the junction tree divided by the number of terminal pairs connected. The framework in [18] used for pairwise spanners with unit lengths has three main steps: 1) construct a layered graph from $G$ to capture the distance constraints and a junction tree rooted at $r$, 2) use the height reduction technique to construct a tree-like graph from the layered graph by paying a small approximation ratio, and 3) solve a corresponding minimum density Steiner label cover problem on the tree-like graph. The main reason for the second and third steps is that the tree-like graph is well-structured, which allows one to find a low-density junction tree by paying a polylogarithmic factor.

To capture distance constraints with negative edge lengths and the flow-based cost in the buy-at-bulk problem, our first two steps (scaling the edge lengths and building the layered graph) require multiple new ideas, which significantly depart from the analysis of [18] in several aspects, as we describe below. Although some of our ideas are natural, we do not believe they are obvious beforehand.

We now present a sketch of the proof of Theorem 6. This is our approximation algorithm for Online Buy-at-bulk Spanner and it removes the dependency on $R$ (i.e., the ratio between the maximum and minimum demand) from previous literature.

In the offline setting, an $\tilde{O}(k^{\epsilon })$-approximation algorithm for Single-source Buy-at-bulk Spanner directly follows by Theorem 12. An offline approximation algorithm for Buy-at-bulk Spanner follows a standard iterative density procedure for directed Steiner forests [16] and spanners [34, 32]. Iteratively picking minimum-density distance-constrained junction trees only pays a factor of $O(\sqrt{k})$. Combining this and Theorem 12 results an offline $\tilde{O}(k^{1/2+\epsilon })$-approximation. Finding an online solution requires several technical modifications. Instead of using an iterative procedure, which inherently uses the global structure of the problem in the offline setting, we construct junction trees in an online fashion similar to online buy-at-bulk [12], by considering all vertices as the candidate junction tree root simultaneously. Before terminal pairs arrive, we pre-process the input graph as follows. To handle distance constraints, we first construct a collection of layered graphs that approximately preserves the edge lengths and captures the distance to (from) each candidate root vertex of the junction tree. Then we use the height reduction technique to construct a forest, which is well-structured for deriving a reduction to the online Steiner label cover problem on the forest. An arriving terminal pair introduces a partial input of the online Steiner label cover problem on the forest, which can be approximately solved online [34]. Ultimately, we recover a solution in the original graph from the Steiner label cover solution in the forest.

We now describe the high-level overview of the proof of Theorem 3. This result gives a sublinear approximation for Buy-at-bulk Spanner. The overall strategy here is to classify all terminal pairs as good or bad based on some parameters and tackle them separately. This approach is followed by multiple publications in the past such as [28, 9, 32, 21]. But all of these results have key differences in their details which give rise to significant differences in their results. Our proof of Theorem 3 also has several seemingly minor changes which require delicate incorporation to achieve our general result.

Similarly to the Steiner forest framework [9, 28] and the buy-at-bulk network design framework [5], we classify the terminal pairs as follows:

• $\mathrm{■}$

  A pair $(s,t)\in D$ is good if the feasible (i.e., satisfying the distance constraint) and cheap (low upfront cost and low pay-per-use cost) $s\mathrm{⤳}t$ paths span a great number of vertices.

• $\mathrm{■}$

  A pair $(s,t)\in D$ is bad otherwise.

Different from the previous literature, our main technical challenge is to accommodate distance constraints. With distance constraints, we have to handle all the cases carefully, without destroying the desired structural properties. The analysis significantly departs from [28, 9, 32, 5] in several aspects, as we describe below.

We describe the proof of Theorem 16. This is our approximation algorithm for Resource-constrained Shortest Path and it allows edge lengths to be negative (as opposed to [47, 43, 44]). We use this result in the proof of Theorem 3. We also believe it is of independent interest since it can be used to extend the results which use [47, 43, 44]).

Recall that for $m$-RCSP, we are given a directed graph with a terminal vertex pair. Each edge is associated with a cost and an $m$-dimensional resource consumption vector where entries can be negative. There is no negative cycle induced by any resource type. We also have an $m$-dimensional budget for the resource consumption. The goal is to find a cheap path to connect the terminal pair without exceeding the budget.

To construct the approximation scheme, we follow the dynamic programming (DP) paradigm in [44]. To approximately preserve feasibility, [44] scales the resource consumption properly, and the DP memorizes the feasible resource consumption patterns while reaching a specific vertex from the source. To accommodate negative resource consumption, the main challenge is the negative resource consumption can be unbounded in terms of the scale for the non-negative consumption. Addressing these challenges requires several modifications. Not only do we construct a larger DP table, this DP table needs a different algorithm since the old algorithm fails when the weights are allowed to be negative. With the assumption that negative cycles do not exist, our DP needs to consider hop counts in a fashion similar to the Bellman-Ford algorithm. The number of resource consumption patterns in our setting depends on the condition numbers ${\gamma }_i$ and this requires some careful analysis.

A well-studied variant of spanners is called the directed $s$-spanner problem, where there is a fixed value $s\ge 1$ called the stretch, and the goal is to find a subgraph with a minimum number of edges such that the distance between every pair of vertices is preserved within a factor of $s$ in the original graph. When the lengths of the edges are uniform and $s=2$, there is a tight $\mathrm{\Theta }(\log n)$-approximation algorithm [26, 46]. When $s=3,4$ there are $\tilde{O}(n^{1/3})$-approximation algorithms [9, 22]. When $s>4$, the best known approximation factor is $\tilde{O}(n^{1/2})$ [9]. The problem is hard to approximate within an $O(2^{{\log }^{1-\epsilon }n})$ factor for $3\le s=O(n^{1-\delta })$ and any $\epsilon ,\delta \in (0,1)$, unless $NP\subseteq DTIME(n^{\mathrm{polylog}n})$ [27]. More general variants consider the pairwise spanner problem [18], and the client-server model [26, 10], where the set of terminals is arbitrary $D=\{(s_i,t_i)\mid i\in [k]\}\subseteq V\times V$, and each terminal pair $(s_i,t_i)$ has its own target distance $d_i$. The goal is to compute a minimum cardinality subgraph in which for each $i$, the distance from $s_i$ to $t_i$ is at most $d_i$. For the pairwise spanner problem with uniform lengths, [18] obtains an $\tilde{O}(n^{3/5+\epsilon })$ approximation. Recently, [32] studied the weighted spanner problem for arbitrary terminal pairs, which has a closer formulation to buy-at-bulk spanners. [34] studied online directed spanners. We refer the reader to the excellent survey [2] for a more comprehensive exposition.

The buy-at-bulk problem has received considerable attention and has been well-studied in the past few decades. Most of the previous buy-at-bulk literature focused on undirected networks, as listed below.

The problem was first introduced in [55], where the subadditive load function was used to capture the economy of scale in network design. [55] showed that the problem is $NP$-hard, and gave an $O(\min \{\log n,\log D_{\max }\})$-approximation algorithm for the single-source problem, where $D_{\max }$ is the maximum demand. When the edge costs are uniform, there is a $\mathrm{𝗉𝗈𝗅𝗒𝗅𝗈𝗀}(n)$-approximation algorithm for the multi-commodity problem [7] and $O(1)$-approximation algorithms for the single-source problem [35, 57, 37]. With non-uniform load functions, the first nontrivial result for the multi-commodity problem was $O(\log D_{\max }\exp (O(\sqrt{\log n\log \log n})))$-approximate [14], later improved to $\mathrm{𝗉𝗈𝗅𝗒𝗅𝗈𝗀}(n)$-approximate [17]; for the single-source problem, there is an $O(\log k)$-approximate algorithm [49]. The buy-at-bulk problem is more intractable on directed graphs. The state-of-the-art is an $\min \{\tilde{O}(k^{1/2+\epsilon }),\tilde{O}(n^{4/5+\epsilon })\}$-approximate algorithm [5]. Even in the special case of directed Steiner forests, previous algorithms only gave $\mathrm{𝗉𝗈𝗅𝗒}(n)$ but sublinear (i.e., $o(n)$) approximation algorithms [9, 18, 28, 1]. On the hardness side, for the undirected buy-at-bulk problem, the multi-commodity problem is $O({\log }^{1/2-\epsilon }n)$-hard to approximate when the costs are general and $O({\log }^{1/4-\epsilon }n)$-hard to approximate when the costs are uniform [4], and the single-source problem is $O(\log \log n)$-hard to approximate [19]. These results are based on the assumption that $NP⊈ZTIME(n^{\mathrm{𝗉𝗈𝗅𝗒𝗅𝗈𝗀}(n)})$. For directed buy-at-bulk, the problem is hard to approximate within an $O(2^{{\log }^{1-\epsilon }n})$ factor assuming that $NP⊈DTIME(n^{\mathrm{𝗉𝗈𝗅𝗒𝗅𝗈𝗀}(n)})$, even in the special case of directed Steiner forests [23].

Note that previous literature, including [31, 12], uses the term length to refer to $\delta (e)$, where the notion is different from ours. In [12], length refers to a global parameter that needs to be minimized. We consider length as a constraint parameter. Furthermore, our setting accounts for three types of costs (two for buy-at-bulk and one for lengths), which is richer than the earlier work on buy-at-bulk and hop-constrained network design (see Section 1.4.4) with two cost functions.

Besides the edge-weighted buy-at-bulk problem, there are other variants, including the node-weighted problem and the prize-collecting problem. In the prize-collecting problem, each terminal pair also has a penalty, and one can choose not to connect the pair and incur the penalty in the cost. Most results are on undirected graphs. For undirected node-weighted buy-at-bulk, there exists a polylogarithmic polynomial-time approximation algorithm [15] and a polylogarithmic quasi-polynomial-time competitive online algorithm [12]. In a more restricted case, i.e., undirected node-weighted Steiner trees, a polylogarithmic approximation algorithm was presented in [45] and a polylogarithmic competitive online algorithm was presented in [50]. Following [50], [41] extends to online undirected node-weighted Steiner forests while [42] extends to the online prize-collecting versions. These results fall under the unifying framework of [3] which utilizes an online primal-dual LP rounding scheme. The work [12] further extends to the online price-collecting buy-at-bulk problem with the same competitive ratio as the standard edge-weighted problem on both directed and undirected graphs. The work [38] considers a metric-based variant of undirected online buy-at-bulk and presents a framework that finds a cheap subgraph (compared to the minimum spanning tree or the optimal Steiner forest) that connects the terminal pairs with low stretch.

A general class of undirected bi-criteria network problems was introduced by [48], where one basic setting is the undirected Steiner tree problem. The goal is to connect a subset of vertices to a specified root vertex. In the bi-criteria problem, the distance from the root to a target vertex is required to be at most the given global threshold. [48] presented a bi-criteria algorithm for undirected Steiner trees that is $O(\log n)$-approximate and violates the distance constraints by a factor of $O(\log n)$. Following [48], [40] extends this result to a more general buy-at-bulk bi-criteria network design problem, where the objective is $\mathrm{𝗉𝗈𝗅𝗒𝗅𝗈𝗀}(n)$-approximate and violates the distance constraints by a factor of $\mathrm{𝗉𝗈𝗅𝗒𝗅𝗈𝗀}(n)$.

[39, 29] studied the tree embedding technique used for undirected network connectivity problems with hop constraints. For a positively weighted graph with a global parameter $h\in [n]$, the hop distance between vertices $u$ and $v$ is the minimum weight among the $u$-$v$-paths using at most $h$ edges. Under some mild assumptions, the tree embedding technique allows a $\mathrm{𝗉𝗈𝗅𝗒𝗅𝗈𝗀}(n)$-approximation by relaxing the hop distance within a $\mathrm{𝗉𝗈𝗅𝗒𝗅𝗈𝗀}(n)$ factor for a rich class of undirected network connectivity problems.

The resource-constrained shortest path problem was introduced in [44]. The input consists of $m$ resource types and a directed graph where each edge is associated with a non-negative cost and a non-negative (for all coordinates) resource consumption vector. The goal is to find a minimum-cost path that connects the single source vertex to the single sink vertex while satisfying the resource constraint. When $m=1$, this problem is equivalent to the restricted shortest path problem [43, 47], which has been extensively used in the literature of spanners [21, 18, 28, 9, 34]. The results of [44] show that when $m$ is a constant, there exists an FPTAS that finds a path with a cost at most the same as the feasible minimum-cost path by violating each budget by a factor of $1+\epsilon$. The FPTAS for $m=2$ is used to solve the weighted spanner problem [32].

We use Minimum-density Distance-constrained Junction Tree as a black box for resolving this case. The following lemma is a slight variant of a standard result in previous literature [9, 28, 32].

To handle this case, we first build a linear program (LP) and solve it.

Intuitively, $x_e$ denotes the edge indicators for $e\in E$, $y_{uv}$ denotes the total flow value that connects $u$ to $v$ via cheap and feasible routes, and $f_p$ denotes the flow value for path $p$. For every $(u,v)\in D_b$, let $\mathrm{\Pi }(u,v)$ be the set of paths $P$ from $u$ to $v$ in $G$ such that $\sigma (P)\le \tau /n^{4/5}$ and $\text{Len}(P)\le \text{Dis}(u,v)$ (i.e., the distance constraints are satisfied). Also, let $\mathrm{\Pi }={\cup }_{(u,v)\in D_b}\mathrm{\Pi }(u,v)$. LP (5) attempts to find a cheap and feasible (resource constraint-wise) solution where all the paths are taken from $\mathrm{\Pi }$. We first use a separation-oracle-base approach to approximately solve LP (5) (described in more detail in Section 2.3), but the problem here is that this solution could have paths that are expensive in the pay-per-use cost $\delta$. We resolve this issue by careful processing based on [5].

Because the optimal set of paths for the pairs in $D_b^3$ (i.e., $P_3^{\ast }=\{P_{uv}^{\ast }\mid (u,v)\in D_b^3\}$) corresponds to a basic feasible solution of LP (5), the objective value of $(\widehat{x},\widehat{y},\widehat{f})$ is at most $(1+\zeta )\cdot \tau$. Now, let $(\check{x},\check{y},\check{f})=(2\widehat{x},\widehat{y},2\widehat{f})$. Set $\check{f_p}=0$ for every path $p$ such that $\delta (p)>n^{4/5}\tau /k$. Then we reduce other $\check{f_p}$ values so that ${\sum }_{p\in \mathrm{\Pi }(u,v)}\check{f_p}=y_{u,v}\forall (u,v)\in D_b$, and also prune the $x_e$ values such that ${\check{x}}_e={\max }_{(u,v)\in D_b}\{{\sum }_{p:e\in P\in {\mathrm{\Pi }}_{(u,v)}}\check{f_p}\}$ for all $e\in E$ (i.e., we prune $x_e$ to make it as small as it can be while ensuring it can handle the necessary flow). This new $(\check{x},\check{y},\check{f})$ is another basic feasible solution to LP (5).

For now, we have ${\sum }_{p\in \mathrm{\Pi }(u,v)}\check{f_p}=y_{u,v}\forall (u,v)\in D_b$; in addition, any path that still has $\check{f_p}>0$ has both cheap investment and cheap maintenance (i.e., $\sigma (P)\le \tau /n^{4/5}$ and $\delta (P)\le n^{4/5}\tau /k$). Furthermore, these paths also satisfy the distance constraint of the demand pair they connect. All we have to do now is to round this solution.