Improved Approximation Algorithms for Capacitated Network Design and Flexible Graph Connectivity

As mentioned above, research on approximation algorithms for Cap-$k$-ECSS was initiated by Goemans et al. [9]. Carr et al. [6], in a seminal paper, introduced a key algorithmic tool for capacitated network design based on the Knapsack-Cover Inequalities (KCI); we discuss KCI in more detail in section 1.4.1. More than a decade later, Chakrabarty et al. [7] used KCI to design an $O(\log n)$ approximation algorithm for Cap-$k$-ECSS. Boyd et al. [5] gave a $\min \{k,2u_{max}\}$-approximation algorithm for Cap-$k$-ECSS, and Bansal [3], based on previous work by Bansal et al. [4] and Williamson et al. [21], gave a $(6\cdot \lceil k/u_{min}\rceil )$-approximation algorithm for Cap-$k$-ECSS.

The model of flexible graph connectivity originated from research in the area of robust optimization. Adjiashvili, Stiller and Zenklusen [2] introduced their model of bulk-robust combinatorial optimization, and designed some approximation algorithms. Later, Adjiashvili, Hommelsheim and Mühlenthaler [1] introduced the $\mathrm{FGC}$ model. Boyd et al. [5] introduced a generalization called the $(p,q)\text{-}\mathrm{FGC}$ model. Boyd et al. [5] presented a $4$-approximation algorithm for $(p,1)\text{-}\mathrm{FGC}$ based on the primal-dual method of Williamson, Goemans, Mihail & Vazirani (WGMV) [21], and a $(q+1)$-approximation algorithm for $(1,q)\text{-}\mathrm{FGC}$; moreover, they gave an $O(q\log n)$-approximation algorithm for $(p,q)\text{-}\mathrm{FGC}$. Subsequently, several interesting results and approximation algorithms have been presented; we summarize some of these recent papers in chronological order. Chekuri and Jain [8] give $O(p)$-approximation algorithms for, respectively, $(p,2)$, $(p,3)$ and $(2p,4)$-FGC, and an $O(q)$-approximation algorithm for $(2,q)\text{-}\mathrm{FGC}$. Bansal et al. [4], among other results, give an $O(1)$-approximation algorithm for $(p,2)\text{-}\mathrm{FGC}$; moreover, they give a 16-approximation algorithm for a related problem called $\mathrm{Cover}\mathrm{Small}\mathrm{Cuts}$. Nutov [17] improves the approximation ratio for $\mathrm{Cover}\mathrm{Small}\mathrm{Cuts}$ from 16 to 10. Bansal [3], and later Nutov [18], give a $6$-approximation algorithm for $\mathrm{Cover}\mathrm{Small}\mathrm{Cuts}$; also, see [20]. Bansal [3] gives an $O(1)$-approximation algorithm for $(p,3)\text{-}\mathrm{FGC}$. Hyatt-Denesik et al. [12], among other results, give approximation algorithms for unit-cost FGC problems with edge-connectivity requirements as well as for unit-cost FGC problems with vertex connectivity requirements. Hommelsheim et al. [11] study a model related to a generalization of FGC called the $(p,q)$-Steiner-Connectivity Preservation problem. Ibrahimpur & Vegh [13] give an $O(\log n)$-approximation algorithm for $(p,q)\text{-}\mathrm{FGC}$.

The Cap-$k$-ECSS problem is as follows: Given an undirected graph $G=(V,E)$ with edge costs $c\in {\mathbb{Q}}_{\ge 0}^E$ and edge capacities $u\in {\mathbb{Z}}_{\ge 0}^E$, find a minimum-cost edge-set $F\subseteq E$ such that the capacity of any cut in $(V,F)$ is at least $k$. Let $u_{min}$ (respectively, $u_{max}$) denote the minimum (respectively, maximum) capacity of an edge in $E$, and assume (w.l.o.g.) that $u_{max}\le k$.

For a graph $G=(V,E)$ and a set of nodes $S\subseteq V$, the cut of $S$, denoted by $\delta (S)$, refers to the set of edges that have exactly one end-node in $S$. Whenever we use the term “cut $\delta (S)$” we mean that $S$ is a subset of $V(G)$. We call a cut $\delta (S)$ non-trivial if $S$ is a nonempty, proper subset of $V$, that is, if $\mathrm{\varnothing }\ne S⊊V$.

The following integer program formulates the Cap-$k$-ECSS problem. It can be viewed as the natural “cut covering” formulation of the problem. It has a binary variable $x_e$ for each edge $e$, with the meaning that an edge $e$ is picked iff $x_e=1$, and, for each non-trivial cut, it has a constraint stating that the capacity of the picked edges in the cut is $\ge k$.

The LP (linear programming) relaxation of the above integer program is obtained by replacing $x_e\in \{0,1\}$ by $0\le x_e\le 1$, $\forall e\in E$. The following well-known example shows that the LP relaxation has an integrality ratio of $\mathrm{\Omega }(k)$; similar examples are given in [6, 7].

Adjiashvili, Hommelsheim and Mühlenthaler [1] introduced the model of Flexible Graph Connectivity that we denote by $\mathrm{FGC}$ as a way to model network design problems where edges have non-uniform reliability. Boyd, Cheriyan, Haddadan and Ibrahimpur [5] introduced a generalization of $\mathrm{FGC}$, called the $(p,q)$-Flexible Graph Connectivity problem, denoted $(p,q)\text{-}\mathrm{FGC}$, where $p$ is an integer denoting the connectivity requirement, and $q$ is an integer denoting the robustness requirement. An instance of $(p,q)\text{-}\mathrm{FGC}$ consists of an undirected graph $G=(V,E)$, where $E$ is partitioned into a set of safe edges $𝒮$ (edges that never fail) and a set of unsafe edges $𝒰$ (edges that may fail), and nonnegative edge-costs $c\in {\mathbb{Q}}_{\ge 0}^E$. A subset $F\subseteq E$ of edges is feasible for the $(p,q)\text{-}\mathrm{FGC}$ problem if for any set $F^{\prime }$ consisting of at most $q$ unsafe edges, the subgraph $(V,F-F^{\prime })$ remains $p$-edge connected. The objective is to find a feasible solution $F$ that minimizes $c(F)={\sum }_{e\in F}{c}_e$.

The following linear program gives a lower bound on the optimal value for $(p,q)$-FGC. Such LP relaxations are discussed in [5] and [8, Section 2]. To motivate the LP relaxation, consider an auxiliary capacitated graph that has the same set of nodes and the same set of edges as the graph of the $(p,q)$-FGC instance. Assign a capacity of $(p+q)$ to each safe edge and a capacity of $p$ to each unsafe edge. Let $k=p(p+q)$ and view the capacitated graph as an instance of the Cap-$k$-ECSS problem. In general, observe that a feasible solution of the $(p,q)$-FGC instance corresponds to a feasible solution of the Cap-$k$-ECSS instance, but not vice-versa. (When either $p=1$ or $q=1$, then a feasible solution of the Cap-$k$-ECSS instance corresponds to a feasible solution of the $(p,q)$-FGC instance.) Each edge $e\in 𝒮\cup 𝒰$ has a variable $x_e$.

Unfortunately, similarly to the LP relaxation for Cap-$k$-ECSS, the above LP relaxation has a large integrality ratio, even for the special case of $(1,q)\text{-}\mathrm{FGC}$. Example 1 can be modified such that for $p=1$ and $q>0$, the above LP relaxation has integrality ratio $(q+1)$.

In this subsection, we describe three of the known tools that we apply together to obtain our main results. Each of these tools has been used on its own (without the other tools) to obtain improvements in the approximation ratio of the Cap-$k$-ECSS problem, but, in our opinion, by combining these tools in the right way, we obtain striking improvements in the approximation ratios for the Cap-$k$-ECSS problem and the $(1,q)\text{-}\mathrm{FGC}$ problem.

The first tool is the algorithmic use of the Knapsack-Cover Inequalities (KCI) for strengthening the LP relaxation of (IP: CapkECSS). This tool was introduced by Carr, Fleischer, Leung & Phillips [6]. The second tool is an $O(1)$ approximation algorithm for the so-called $\mathrm{Cover}\mathrm{Small}\mathrm{Cuts}$ problem. This tool was introduced by Bansal, Cheriyan, Grout & Ibrahimpur [4]. The third tool is Jain’s iterative rounding method, [14].

Our first result is an $O(\log k/u_{min})$ approximation algorithm for the Cap-$k$-ECSS problem. Thus, we asymptotically improve upon the previous best approximation ratio of $\min (O(\log n),k,2u_{max},6\cdot \lceil k/u_{min}\rceil )$ whenever $\log (k/u_{min})=o(\log n)$ and $u_{max}$ is sufficiently large.

Before sketching our approximation algorithm for general instances of Cap-$k$-ECSS, let us focus on the special case of two capacities $1$ and $k$. Let $E^{(1)}$ be the set of unit-capacity edges, and let $E^{(k)}$ be the set of edges of capacity $k$. For expository reasons (and glossing over some critical points), let us assume that we can find, in polynomial time, an optimal solution $x^{\ast }$ of (KCLP: CapkECSS), the LP with KCI. Thus, we have $c(x^{\ast })=\text{LP}{}_{\text{opt}}$, where $c(x^{\ast })={\sum }_e{c}_e{x}_e$ is the cost of $x^{\ast }$. Let $E_{high}^{(1)}=\{e\in E^{(1)}:x_e^{\ast }\ge 1/2\}$; this is the set of unit-capacity edges that are assigned values of $1/2$ or more by the LP solution $x^{\ast }$. Let $E_{low}^{(1)}=E^{(1)}-E_{high}^{(1)}$ (the set of unit-capacity edges with $x^{\ast }$-values less than $1/2$). We call a non-trivial cut $\delta (S)$ a small cut if

in other words, a non-trivial cut is defined to be small if the fractional capacity contributed by the unit-capacity edges is less than the requirement of $k$ even after rounding up edges in $E_{high}^{(1)}$ to have $x$-value one and scaling up the $x$-value of each edge in $E_{low}^{(1)}$ by factor $2$. We construct an instance of $\mathrm{Cover}\mathrm{Small}\mathrm{Cuts}$ with small cuts as defined above, and we define the link-set of this instance to be $E^{(k)}$. To handle the small cuts, we apply the knapsack-cover inequalities to show that the solution $x^{\ast }$ restricted to edges of capacity $k$ and scaled up by a factor of $2$ (i.e., $2x_{E^{(k)}}^{\ast }$) constitutes a feasible solution to the LP relaxation of the $\mathrm{Cover}\mathrm{Small}\mathrm{Cuts}$ instance. This is the critical point where our algorithm and analysis relies on the knapsack-cover inequalities. We can thus pick a set $E_{picked}^{(k)}$ of edges of capacity $k$ by applying the $6$-approximation algorithm of [3, 4, 21] to this instance of the $\mathrm{Cover}\mathrm{Small}\mathrm{Cuts}$ problem; note that the cost of $E_{picked}^{(k)}$ is at most $6$ times the cost of $2x_{E^{(k)}}^{\ast }$. After this step, we contract the connected components formed by the edges in $E_{picked}^{(k)}$, and get a new instance that does not have any small cuts. Since there are no small cuts, every non-trivial cut $\delta (S)$ satisfies the inequality $|E_{high}^{(1)}\cap \delta (S)|+{\sum }_{e\in E_{low}^{(1)}\cap \delta (S)}2x_e^{\ast }\ge k$. Therefore, we get a feasible solution for the LP relaxation of the $f$-connectivity problem where $f(S)=k$ for every non-empty set $S⊊V$, by picking all edges in $E_{high}^{(1)}$ and scaling up $x^{\ast }$ restricted to $E_{low}^{(1)}$ by a factor of $2$. Since $f$ is weakly supermodular, we can apply Jain’s iterative rounding method [14] to solve this $f$-connectivity problem and obtain a $2$-approximate solution, giving us an integral solution whose cost is at most $4$ times the cost of $x^{\ast }$ restricted to unit-capacity edges. Thus, we get an integral solution whose total cost is at most $6\cdot 2\cdot \text{LP}{}_{\text{opt}}$.

Let us recap the new algorithmic lever we deployed above. We partitioned the edges according to their capacities into the set of low-capacity edges and the set of high-capacity edges; let $E^{big}$ denote the latter set. Then we defined an instance of $\mathrm{Cover}\mathrm{Small}\mathrm{Cuts}$ whose small cuts were defined using the low-capacity edges and rounding up (and/or scaling up) the fractional capacity contribution $u_e{x}_e^{\ast }$ of each of these edges $e$; moreover, we defined the links (of the $\mathrm{Cover}\mathrm{Small}\mathrm{Cuts}$ instance) to be the high-capacity edges. The small cuts identified above are precisely the cuts where the LP solution $x^{\ast }$ has not invested sufficient fractional capacity in the low-capacity edges to cover the cuts. For these cuts, the knapsack-cover inequalities ensured that $x^{\ast }$ restricted to the high-capacity edges and scaled up by a small constant, say, $\eta$, (i.e., $\eta x_{E^{big}}^{\ast }$) forms a feasible solution to the LP relaxation of the $\mathrm{Cover}\mathrm{Small}\mathrm{Cuts}$ instance. Based on this, we applied the $6$-approximation algorithm of [3, 4, 21] to find a set of high-capacity edges of cost $\le 6\eta c(x_{E^{big}}^{\ast })$ that covers all the small cuts.

Now, let us sketch an extension of the above method that gives an $O(\log k)$-approximation algorithm for Cap-$k$-ECSS. As above, let us assume that we can find, in polynomial time, an optimal solution $x^{\ast }$ of (KCLP: CapkECSS), the LP with KCI. Thus, we have $c(x^{\ast })=\text{LP}{}_{\text{opt}}$. Throughout the execution of the algorithm, we maintain a set of edges $E_{cur}$ acting as our current solution. We begin with $E_{cur}=\{e\in E:x_e^{\ast }\ge 1/2\}$. Define $T=\lceil \log k\rceil$ and for $j=1,2,\mathrm{\dots },T$, define . Ideally, we wish to apply $T$ iterations, and, in each iteration, we wish to apply the above algorithmic lever $O(1)$ times. In more detail, in the $i$th-iteration, we could take the edges of capacity $\le 2^{T-i}$ to be the low-capacity edges and the edges of capacity $>2^{T-i}$ to be the high-capacity edges; that is, $E_{T-i}$ is the set of low-capacity edges and $E-E_{T-i}$ is the set of high-capacity edges. Then, we could define an instance of $\mathrm{Cover}\mathrm{Small}\mathrm{Cuts}$ where we could define the small-cuts to be the non-trivial cuts $\delta (S)$ such that , and we could take the link-set (for the $\mathrm{Cover}\mathrm{Small}\mathrm{Cuts}$ instance) to be the set of high-capacity edges, $E-E_{T-i}$. Although we can apply the algorithmic lever and find an integral cover of the small cuts using the edges in $E-E_{T-i}$ such that the cost of the integral cover is $O(1)c(x_{E-E_{T-i}}^{\ast })$, we run into a difficulty. The capacity of an edge in $E-E_{T-i}$ could be as small as $\mathrm{\Theta }(2^{T-i})$, hence, by adding just one of these edges to a small cut $\delta (S)$ we cannot guarantee that the capacity of $\delta (S)$ is augmented to become $\ge k$. Thus, our algorithm and analysis, presented in section 3, have further steps; a deeper analysis is required to show that our algorithm finds an integral solution of cost $O(\log k)\cdot \text{LP}{}_{\text{opt}}$. Moreover, we improve the approximation ratio from $O(\log k)$ to $O(\log (k/u_{min}))$.

Recall that the $(1,q)\text{-}\mathrm{FGC}$ problem can be formulated as a special case of Cap-$k$-ECSS with two capacities (the unsafe edges have unit capacity and the safe edges have capacity $k=(q+1)$). Clearly, the $O(1)$-approximation algorithm sketched above applies to the $(1,q)\text{-}\mathrm{FGC}$ problem. Our next result improves the approximation ratio to $8$, thus improving on the previous best $(q+1)$-approximation algorithm for $(1,q)\text{-}\mathrm{FGC}$, [5].

Moreover, we present $O(1)$-approximate reductions between the $(2,q)\text{-}\mathrm{FGC}$ problem and the $2\text{-}\mathrm{Cover}\mathrm{Small}\mathrm{Cuts}$ problem. The following two results summarize the two reductions; the details are omitted due to space constraints; see the arXiv version of this paper.

For the sake of readability and accessibility, we present our $8$-approximation algorithm for $(1,q)\text{-}\mathrm{FGC}$ in the next section, and we defer the presentation of our improved approximation algorithm for Cap-$k$-ECSS to section 3. Due to space constraints, our remaining results are omitted but are presented in the arXiv version of this paper.