Search

A classic result of Williamson, Goemans, Mihail, and Vazirani [STOC 1993: 708-717] states that the problem of covering an uncrossable set family by a min-cost edge set admits approximation ratio $2$, by a primal-dual algorithm with a reverse delete phase. Recently, Bansal, Cheriyan, Grout, and Ibrahimpur [ICALP 2023: 15:1-15:19] showed that this algorithm achieves approximation ratio $16$ for a larger class of set families, that have much weaker uncrossing properties. In this paper we will refine their analysis and show an approximation ratio of $10$. This also improves approximation ratios for several variants of the Capacitated $k$-Edge Connected Spanning Subgraph problem., Comment: arXiv admin note: text overlap with arXiv:2307.08270

In the Activation Edge-Multicover problem we are given a multigraph $G=(V,E)$ with activation costs $\{c_{e}^u,c_{e}^v\}$ for every edge $e=uv \in E$, and degree requirements $r=\{r_v:v \in V\}$. The goal is to find an edge subset $J \subseteq E$ of minimum activation cost $\sum_{v \in V}\max\{c_{uv}^v:uv \in J\}$,such that every $v \in V$ has at least $r_v$ neighbors in the graph $(V,J)$. Let $k= \max_{v \in V} r_v$ be the maximum requirement and let $\theta=\max_{e=uv \in E} \frac{\max\{c_e^u,c_e^v\}}{\min\{c_e^u,c_e^v\}}$ be the maximum quotient between the two costs of an edge. For $\theta=1$ the problem admits approximation ratio $O(\log k)$. For $k=1$ it generalizes the Set Cover problem (when $\theta=\infty$), and admits a tight approximation ratio $O(\log n)$. This implies approximation ratio $O(k \log n)$ for general $k$ and $\theta$, and no better approximation ratio was known. We obtain the first logarithmic approximation ratio $O(\log k +\log\min\{\theta,n\})$, that bridges between the two known ratios -- $O(\log k)$ for $\theta=1$ and $O(\log n)$ for $k=1$. This implies approximation ratio $O\left(\log k +\log\min\{\theta,n\}\right) +\beta \cdot (\theta+1)$ for the Activation $k$-Connected Subgraph problem, where $\beta$ is the best known approximation ratio for the ordinary min-cost version of the problem.

In the $Activation$ $k$ $Disjoint$ $st$-$Paths$ ($Activation$ $k$-$DP$) problem we are given a graph $G=(V,E)$ with activation costs $\{c_{uv}^u,c_{uv}^v\}$ for every edge $uv \in E$, a source-sink pair $s,t \in V$, and an integer $k$. The goal is to compute an edge set $F \subseteq E$ of $k$ internally node disjoint $st$-paths of minimum activation cost $\displaystyle \sum_{v \in V}\max_{uv \in E}c_{uv}^v$. The problem admits an easy $2$-approximation algorithm. Alqahtani and Erlebach [CIAC, pages 1-12, 2013] claimed that Activation 2-DP admits a $1.5$-approximation algorithm. Their proof has an error, and we will show that the approximation ratio of their algorithm is at least $2$. We will then give a different algorithm with approximation ratio $1.5$.

A set family ${\cal F}$ is $uncrossable$ if $A \cap B,A \cup B \in {\cal F}$ or $A \setminus B,B \setminus A \in {\cal F}$ for any $A,B \in {\cal F}$. A classic result of Williamson, Goemans, Mihail, and Vazirani [STOC 1993:708-717] states that the problem of covering an uncrossable set family by a min-cost edge set admits approximation ratio $2$, by a primal-dual algorithm. They asked whether this result extends to a larger class of set families and combinatorial optimization problems. We define a new class of $semi$-$uncrossable$ $set$ $families$, when for any $A,B \in {\cal F}$ we have that $A \cap B \in {\cal F}$ and one of $A \cup B,A \setminus B ,B \setminus A$ is in ${\cal F}$, or $A \setminus B,B \setminus A \in {\cal F}$. We will show that the Williamson et al. algorithm extends to this new class of families and identify several ``non-uncrossable'' algorithmic problems that belong to this class. In particular, we will show that the union of an uncrossable family and a monotone family, or of an uncrossable family that has the disjointness property and a proper family, is a semi-uncrossable family, that in general is not uncrossable. For example, our result implies approximation ratio $2$ for the problem of finding a min-cost subgraph $H$ such that $H$ contains a Steiner forest and every connected component of $H$ contains at least $k$ nodes from a given set $T$ of terminals.

We consider the following two variants of the Capacitated $k$-Edge Connected Subgraph} (Cap-k-ECS) problem. Near Min-Cuts Cover: Given a graph $G=(V,E)$ with edge costs and $E_0 \subseteq E$, find a min-cost edge set $J \subseteq E \setminus E_0$ that covers all cuts with at most $k-1$ edges of the graph $G_0=(V,E_0)$. We obtain approximation ratio $k-\lambda_0+1+\epsilon$, improving the ratio $2\min\{k-\lambda_0,8\}$ of Bansal, Cheriyan, Grout, and Ibrahimpur for $k-\lambda_0 \leq 14$,where $\lambda_0$ is the edge connectivity of $G_0$. $(k,q)$-Flexible Graph Connectivity ($(k,q)$-FGC): Given a graph $G=(V,E)$ with edge costs and a set $U \subseteq E$ of ''unsafe'' edges and integers $k,q$, find a min-cost subgraph $H$ of $G$ such that every cut of $H$ has at least $k$ safe edges or at least $k+q$ edges. We show that $(k,1)$-FGC admits approximation ratio $3.5+\epsilon$ if $k$ is odd (improving the previous ratio $4$), and that $(k,2)$-FGC admits approximation ratio $6$ if $k$ is even and $7+\epsilon$ if $k$ is odd (improving the previous ratio $20$).

One of the most important and well-studied settings for network design is edge-connectivity requirements. This encompasses uniform demands such as the Minimum $k$-Edge-Connected Spanning Subgraph problem as well as nonuniform demands such as the Survivable Network Design problem (SND). In a recent paper by [Dinitz, Koranteng, Kortsarz APPROX '22] , the authors observed that a weakness of these formulations is that it does not enable one to consider fault-tolerance in graphs that have just a few small cuts. To remedy this, they introduced new variants of these problems under the notion "relative" fault-tolerance. Informally, this requires not that two nodes are connected if there are a bounded number of faults (as in the classical setting), but that two nodes are connected if there are a bounded number of faults and the two nodes are connected in the underlying graph post-faults. The problem is already highly non-trivial even for the case of a single demand. Due to difficulties introduced by this new notion of fault-tolerance, the results in [Dinitz, Koranteng, Kortsarz APPROX '22] are quite limited. For the Relative Survivable Network Design problem (RSND), when the demands are not uniform they give a nontrivial result only when there is a single demand with a connectivity requirement of $3$: a non-optimal $27/4$-approximation. We strengthen this result in two significant ways: We give a $2$-approximation for RSND where all requirements are at most $3$, and a $2^{O(k^2)}$-approximation for RSND with a single demand of arbitrary value $k$. To achieve these results, we first use the "cactus representation'' of minimum cuts to give a lossless reduction to normal SND. Second, we extend the techniques of [Dinitz, Koranteng, Kortsarz APPROX '22] to prove a generalized and more complex version of their structure theorem, which we then use to design a recursive approximation algorithm., Comment: 34 pages, 4 figures

A graph $G$ is $k$-out-connected from its node $s$ if it contains $k$ internally disjoint $sv$-paths to every node $v$; $G$ is $k$-connected if it is $k$-out-connected from every node. In connectivity augmentation problems the goal is to augment a graph $G_0=(V,E_0)$ by a minimum costs edge set $J$ such that $G_0 \cup J$ has higher connectivity than $G_0$. In the $k$-Out-Connectivity Augmentation ($k$-OCA) problem, $G_0$ is $(k-1)$-out-connected from $s$ and $G_0 \cup J$ should be $k$-out-connected from $s$; in the $k$-Connectivity Augmentation ($k$-CA) problem $G_0$ is $(k-1)$-connected and $G_0 \cup J$ should be $k$-connected. The parameterized complexity status of these problems was open even for $k=3$ and unit costs. We will show that $k$-OCA and $3$-CA can be solved in time $9^p \cdot n^{O(1)}$, where $p$ is the size of an optimal solution. Our paper is the first that shows fixed parameter tractability of a $k$-node-connectivity augmentation problem with high values of $k$. We will also consider the $(2,k)$-Connectivity Augmentation problem where $G_0$ is $(k-1)$-edge-connected and $G_0 \cup J$ should be both $k$-edge-connected and $2$-connected. We will show that this problem can be solved in time $9^p \cdot n^{O(1)}$, and for unit costs approximated within $1.892$.

In minimum power network design problems we are given an undirected graph $G=(V,E)$ with edge costs $\{c_e:e \in E\}$. The goal is to find an edge set $F\subseteq E$ that satisfies a prescribed property of minimum power $p_c(F)=\sum_{v \in V} \max \{c_e: e \in F \mbox{ is incident to } v\}$. In the Min-Power $k$ Edge Disjoint $st$-Paths problem $F$ should contains $k$ edge disjoint $st$-paths. The problem admits a $k$-approximation algorithm, and it was an open question whether it admits approximation ratio sublinear in $k$ even for unit costs. We give a $2\sqrt{2k}$-approximation algorithm for general costs.

In activation network design problems we are given an undirected graph $G=(V,E)$ and a pair of activation costs $\{c_e^u,c_e^v\}$ for each $e=uv \in E$. The goal is to find an edge set $F \subseteq E$ that satisfies a prescribed property of minimum activation cost $\tau(F)=\sum_{v \in V} \max \{c_e^v: e \in F \mbox{ is incident to } v\}$. In the Activation $k$ Disjoint Paths problem we are given $s,t \in V$ and an integer $k$, and seek an edge set $F \subseteq E$ of $k$ internally disjoint $st$-paths of minimum activation cost. The problem admits an easy $2$-approximation algorithm. However, it was an open question whether the problem is in P even for $k=2$ and power activation costs, when $c_e^u=c_e^v$ for all $e=uv \in E$. Here we will answer this question by giving a polynomial time algorithm using linear programing. We will also mention several consequences, among them a polynomial time algorithm for the Activation 2 Edge Disjoint Paths problem, and improved approximation ratios for the Min-Power $k$-Connected Subgraph problem., Comment: The paper has an error - the proof of Lemma 7 is not correct

Let $\kappa(s,t)$ denote the maximum number of internally disjoint $st$-paths in an undirected graph $G$. We consider designing a compact data structure that answers $k$-bounded node connectivity queries: given $s,t \in V$ return $\min\{\kappa(s,t),k+1\}$. A trivial data structure has space $O(n^2)$ and query time $O(1)$. A data structure of Hsu and Lu has space $O(k^2n)$ and query time $O(\log k)$,and a randomized data structure of Iszak and Nutov has space $O(kn\log n)$ and query time $O(k \log n)$. We extend the Hsu-Lu data structure to answer queries in time $O(1)$. In parallel to our work, Pettie, Saranurak and Yin extended the Iszak-Nutov data structure to answer queries in time $O(\log n)$. Our data structure is more compact for $k<\log n$, and our query time is always better. We then augment our data structure by a list of cuts that enables to return a pointer to a minimum $st$-cut in the list (or to a cut of size $\leq k$) whenever $\kappa(s,t) \leq k$. A trivial data structure has cut list size $n(n-1)/2$, and cut query time $O(1)$, while the Pettie, Saranurak and Yin data structure has list size $O(kn \log n)$ and cut query time $O(\log n)$. We show that $O(kn)$ cuts suffice to return an $st$-cut of size $\leq k$, and a list of $O(k^2 n)$ cuts contains a minimum $st$-cut for every $s,t \in V$. In the case when $S$ is a node subset with $\kappa(s,t) \geq k$ for all $s,t \in V$, we show that $3|S|$ cuts suffice, and that these cuts can be partitioned into $O(k)$ laminar families. Thus using space $O(kn)$ we can answers each connectivity and cut queries for $s,t \in S$ in $O(1)$ time, generalizing and substantially simplifying the proof of a result of Pettie and Yin for the case $|S|=V$.

In Connectivity Augmentation problems we are given a graph $H=(V,E_H)$ and an edge set $E$ on $V$, and seek a min-size edge set $J \subseteq E$ such that $H \cup J$ has larger edge/node connectivity than $H$. In the Edge-Connectivity Augmentation problem we need to increase the edge-connectivity by $1$. In the Block-Tree Augmentation problem $H$ is connected and $H \cup S$ should be $2$-connected. In Leaf-to-Leaf Connectivity Augmentation problems every edge in $E$ connects minimal deficient sets. For this version we give a simple combinatorial approximation algorithm with ratio $5/3$, improving the previous $1.91$ approximation that applies for the general case. We also show by a simple proof that if the Steiner Tree problem admits approximation ratio $\alpha$ then the general version admits approximation ratio $1+\ln(4-x)+\epsilon$, where $x$ is the solution to the equation $1+\ln(4-x)=\alpha+(\alpha-1)x$. For the currently best value of $\alpha=\ln 4+\epsilon$ this gives ratio $1.942$. This is slightly worse than the best ratio $1.91$, but has the advantage of using Steiner Tree approximation as a "black box", giving ratio $< 1.9$ if ratio $\alpha \leq 1.35$ can be achieved. In the Element Connectivity Augmentation problem we are given a graph $G=(V,E)$, $S \subseteq V$, and connectivity requirements $\{r(u,v):u,v \in S\}$. The goal is to find a min-size set $J$ of new edges on $S$ such that for all $u,v \in S$ the graph $G \cup J$ contains $r(u,v)$ $uv$-paths such that no two of them have an edge or a node in $V \setminus S$ in common. The problem is NP-hard even when $\max_{u,v \in S} r(u,v)=2$. We obtain approximation ratio $3/2$, improving the previous ratio $7/4$.

We consider the directed Min-Cost Rooted Subset $k$-Edge-Connection problem: given a digraph $G=(V,E)$ with edge costs, a set $T \subseteq V$ of terminals, a root node $r$, and an integer $k$, find a min-cost subgraph of $G$ that contains $k$ edge disjoint $rt$-paths for all $t \in T$. The case when every edge of positive cost has head in $T$ admits a polynomial time algorithm due to Frank [Discret. Appl. Math. 157(6):1242-1254, 2009], and the case when all positive cost edges are incident to $r$ is equivalent to the $k$-Multicover problem. Chan, Laekhanukit, Wei, and Zhang [APPROX/RANDOM, 63:1-63:20, 2020] gave an LP-based $O(\ln k \ln |T|)$-approximation algorithm for quasi-bipartite instances, when every edge in $G$ has an end (tail or head) in $T \cup \{r\}$. We give a simple combinatorial algorithm with the same ratio for a more general problem of covering an arbitrary $T$-intersecting supermodular set function by a minimum cost edge set, and for the case when only every positive cost edge has an end in $T \cup \{r\}$.

We consider the problem of maximizing a non-negative monotone submodular function subject to a knapsack constraint, which is also known as the Budgeted Submodular Maximization (BSM) problem. Sviridenko (2004) showed that by guessing 3 appropriate elements of an optimal solution, and then executing a greedy algorithm, one can obtain the optimal approximation ratio of $\alpha =1-1/e\approx 0.632$ for BSM. However, the need to guess (by enumeration) 3 elements makes the algorithm of Sviridenko impractical as it leads to a time complexity of $O(n^5)$ (which can be slightly improved using the thresholding technique of Badanidiyuru & Vondrak (2014), but only to roughly $O(n^4)$). Our main results in this paper show that fewer guesses suffice. Specifically, by making only 2 guesses, we get the same optimal approximation ratio of $\alpha$ with an improved time complexity of roughly $O(n^3)$. Furthermore, by making only a single guess, we get an almost as good approximation ratio of $0.6174>0.9767\alpha$ in roughly $O(n^2)$ time. Prior to our work, the only algorithms that were known to obtain an approximation ratio close to $\alpha$ for BSM were the algorithm of Sviridenko and an algorithm of Ene & Nguyen (2019) that achieves $(\alpha-\epsilon)$-approximation. However, the algorithm of Ene & Nguyen requires ${(1/\epsilon)}^{O(1/\epsilon^4)}n\log^2 n$ time, and hence, is of theoretical interest only as ${(1/\epsilon)}^{O(1/\epsilon^4)}$ is huge even for moderate values of $\epsilon$. In contrast, all the algorithms we analyze are simple and parallelizable, which makes them good candidates for practical use. Recently, Tang et al. (2020) studied a simple greedy algorithm that already has a long research history, and proved that its approximation ratio is at least 0.405. We improve over this result, and show that the approximation ratio of this algorithm is within the range [0.427, 0.462]., Comment: 31 pages, 1 figure

We consider network design problems in which we are given a graph and seek a min-size $2$-connected subgraph that satisfies a prescribed property. $\bullet$ In the 1-Connectivity Augmentation problem the goal is to augment a connected graph by a min-size edge subset of a specified edge set such that the augmented graph is $2$-connected. We breach the natural ratio of $2$ for this problem and also for the more general Crossing Family Cover problem. $\bullet$ In the $2$-Connected Dominating Set problem we seek a minimum size $2$-connected subgraph that dominates all nodes. We give the first non-trivial approximation algorithm for this problem, with expected ratio $O(\sigma\log^3 n)$, where $\sigma=O(\log n \cdot\log\log n\cdot(\log\log\log n)^{3})$. The unifying technique of both results is a reduction to the Subset Steiner Connected Dominating Set problem. Such a reduction was known for edge-connectivity, and we extend it to $2$-node connectivity problems. We show that the same method can be used to obtain easily polylogarithmic approximation ratios that are not too far from the best known ones for several other problems.

In the Connected Dominating Set problem we are given a graph $G=(V,E)$ and seek a minimum size dominating set $S \subseteq V$ such that the subgraph $G[S]$ of $G$ induced by $S$ is connected. In the $2$-Edge-Connected Dominating Set problem $G[S]$ should be $2$-edge-connected. We give the first non-trivial approximation algorithm for this problem, with expected approximation ratio $\tilde{O}(\log^2n)$.

We study two problems that seek a subtree $T$ of a graph $G=(V,E)$ such that $T$ satisfies a certain property and has minimal maximum degree. - In the Min-Degree Group Steiner Tree problem we are given a collection ${\cal S}$ of groups (subsets of $V$) and $T$ should contain a node from every group. - In the Min-Degree Steiner $k$-Tree problem we are given a set $R$ of terminals and an integer $k$, and $T$ should contain at least $k$ terminals. We show that if the former problem admits approximation ratio $\rho$ then the later problem admits approximation ratio $\rho \cdot O(\log k)$. For bounded treewidth graphs, we obtain approximation ratio $O(\log^3 n)$ for Min-Degree Group Steiner Tree. In the more general Bounded Degree Group Steiner Tree problem we are also given edge costs and degree bounds $\{b(v):v \in V\}$, and $T$ should obey the degree constraints $deg_T(v) \leq b(v)$ for all $v \in V$. We give a bicriteria $(O(\log N \log |{\cal S}|),O(\log^2 n))$-approximation algorithm for this problem on tree inputs, where $N$ is the size of the largest group, generalizing the approximation of Garg, Konjevod, and Ravi for the case without degree bounds.

A subset $S$ of nodes in a graph $G$ is a $k$-connected $m$-dominating set ($(k,m)$-cds) if the subgraph $G[S]$ induced by $S$ is $k$-connected and every $v \in V \setminus S$ has at least $m$ neighbors in $S$. In the $k$-Connected $m$-Dominating Set ($(k,m)$-CDS) problem the goal is to find a minimum weight $(k,m)$-cds in a node-weighted graph. For $m \geq k$ we obtain the following approximation ratios. For general graphs our ratio $O(k \ln n)$ improves the previous best ratio $O(k^2 \ln n)$ and matches the best known ratio for unit weights. For unit disc graphs we improve the ratio $O(k \ln k)$ to $\min\left\{\frac{m}{m-k},k^{2/3}\right\} \cdot O(\ln^2 k)$ -- this is the first sublinear ratio for the problem, and the first polylogarithmic ratio $O(\ln^2 k)/\epsilon$ when $m \geq (1+\epsilon)k$; furthermore, we obtain ratio $\min\left\{\frac{m}{m-k},\sqrt{k}\right\} \cdot O(\ln^2 k)$ for uniform weights. These results are obtained by showing the same ratios for the Subset $k$-Connectivity problem when the set $T$ of terminals is an $m$-dominating set with $m \geq k$.

We obtain approximation ratio $2(2+\frac{1}{\ell})$ for the (undirected) $k$-Connected Subgraph problem, where $\ell \approx \frac{1}{2} (\log_k n-1)$ is the largest integer such that $2^{\ell-1} k^{2\ell+1} \leq n$. For large values of $n$ this improves the $6$-approximation of Cheriyan and V\'egh when $n =\Omega(k^3)$, which is the case $\ell=1$. For $k$ bounded by a constant we obtain ratio $4+\epsilon$. For large values of $n$ our ratio matches the best known ratio $4$ for the augmentation version of the problem, as well as the best known ratios for $k=6,7$. Similar results are shown for the problem of covering an arbitrary crossing supermodular biset function.

What approximation ratio can we achieve for the Facility Location problem if whenever a client $u$ connects to a facility $v$,the opening cost of $v$ is at most $\theta$ times the service cost of $u$? We show that this and many other problems are a particular case of the Activation Edge-Cover problem. Here we are given a multigraph $G=(V,E)$, a set $R \subseteq V$ of terminals, and thresholds $\{t^e_u,t^e_v\}$ for each $uv$-edge $e \in E$. The goal is to find an assignment ${\bf a}=\{a_v:v \in V\}$ to the nodes minimizing $\sum_{v \in V} a_v$, such that the edge set $E_{\bf a}=\{e=uv: a_u \geq t^e_u, a_v \geq t^e_v\}$ activated by ${\bf a}$ covers $R$. We obtain ratio $1+\omega(\theta) \approx \ln \theta-\ln \ln \theta$ for the problem, where $\omega(\theta)$ is the root of the equation $x+1=\ln(\theta/x)$ and $\theta$ is a problem parameter. This result is based on a simple generic algorithm for the problem of minimizing a sum of a decreasing and a sub-additive set functions, which is of independent interest. As an application, we get that the above variant of Facility Location admits ratio $1+\omega(\theta)$; if for each facility all service costs are identical then we show a better ratio $\displaystyle 1+\max_{k \geq 1} \frac{H_k-1}{1+k/\theta}$, where $H_k=\sum_{i=1}^k 1/i$. For the Min-Power Edge-Cover problem we improve the ratio $1.406$ of Calinescu et. al. (achieved by iterative randomized rounding) to $1+\omega(1)<1.2785$. For unit thresholds we improve the ratio $73/60 \approx 1.217$ to $\frac{1555}{1347} \approx 1.155$.

In the Tree Augmentation problem we are given a tree $T=(V,F)$ and a set $E \subseteq V \times V$ of edges with positive integer costs $\{c_e:e \in E\}$. The goal is to augment $T$ by a minimum cost edge set $J \subseteq E$ such that $T \cup J$ is $2$-edge-connected. We obtain the following results. Recently, Adjiashvili [SODA 17] introduced a novel LP for the problem and used it to break the $2$-approximation barrier for instances when the maximum cost $M$ of an edge in $E$ is bounded by a constant; his algorithm computes a $1.96418+\epsilon$ approximate solution in time $n^{{(M/\epsilon^2)}^{O(1)}}$. Using a simpler LP, we achieve ratio $\frac{12}{7}+\epsilon$ in time $2^{O(M/\epsilon^2)} poly(n)$.This gives ratio better than $2$ for logarithmic costs, and not only for constant costs. One of the oldest open questions for the problem is whether for unit costs (when $M=1$) the standard LP-relaxation, so called Cut-LP, has integrality gap less than $2$. We resolve this open question by proving that for unit costs the integrality gap of the Cut-LP is at most $28/15=2-2/15$. In addition, we will prove that another natural LP-relaxation, that is much simpler than the ones in previous work, has integrality gap at most $7/4$.

A graph is $k$-connected if it has $k$ internally-disjoint paths between every pair of nodes. A subset $S$ of nodes in a graph $G$ is a $k$-connected set if the subgraph $G[S]$ induced by $S$ is $k$-connected; $S$ is an $m$-dominating set if every $v \in V \setminus S$ has at least $m$ neighbors in $S$. If $S$ is both $k$-connected and $m$-dominating then $S$ is a $k$-connected $m$-dominating set, or $(k,m)$-cds for short. In the $k$-Connected $m$-Dominating Set ($(k,m)$-CDS) problem the goal is to find a minimum weight $(k,m)$-cds in a node-weighted graph. We consider the case $m \geq k$ and obtain the following approximation ratios. For unit disc-graphs we obtain ratio $O(k\ln k)$, improving the previous ratio $O(k^2 \ln k)$. For general graphs we obtain the first non-trivial approximation ratio $O(k^2 \ln n)$.

In the Tree Augmentation Problem (TAP) the goal is to augment a tree $T$ by a minimum size edge set $F$ from a given edge set $E$ such that $T \cup F$ is $2$-edge-connected. The best approximation ratio known for TAP is $1.5$. In the more general Weighted TAP problem, $F$ should be of minimum weight. Weighted TAP admits several $2$-approximation algorithms w.r.t. to the standard cut LP-relaxation, but for all of them the performance ratio of $2$ is tight even for TAP. The problem is equivalent to the problem of covering a laminar set family. Laminar set families play an important role in the design of approximation algorithms for connectivity network design problems. In fact, Weighted TAP is the simplest connectivity network design problem for which a ratio better than $2$ is not known. Improving this "natural" ratio is a major open problem, which may have implications on many other network design problems. It seems that achieving this goal requires finding an LP-relaxation with integrality gap better than $2$, which is a long time open problem even for TAP. In this paper we introduce such an LP-relaxation and give an algorithm that computes a feasible solution for TAP of size at most $1.75$ times the optimal LP value. This gives some hope to break the ratio $2$ for the weighted case. Our algorithm computes some initial edge set by solving a partial system of constraints that form the integral edge-cover polytope, and then applies local search on $3$-leaf subtrees to exchange some of the edges and to add additional edges. Thus we do not need to solve the LP, and the algorithm runs roughly in time required to find a minimum weight edge-cover in a general graph., Comment: arXiv admin note: substantial text overlap with arXiv:1507.02799

The Tree Augmentation Problem (TAP) is: given a connected graph $G=(V,{\cal E})$ and an edge set $E$ on $V$ find a minimum size subset of edges $F \subseteq E$ such that $(V,{\cal E} \cup F)$ is $2$-edge-connected. In the conference version \cite{EFKN-APPROX} was sketched a $1.5$-approximation algorithm for the problem. Since a full proof was very complex and long, the journal version was cut into two parts. In the first part \cite{EFKN-TALG} was only proved ratio $1.8$. An attempt to simplify the second part produced an error in \cite{EKN-IPL}. Here we give a correct, different, and self contained proof of the ratio $1.5$, that is also substantially simpler and shorter than the previous proofs.

We consider low connectivity variants of the Survivable Network with Minimum Number of Steiner Points (SN-MSP) problem: given a finite set $R$ of terminals in a metric space (M,d), a subset $B \subseteq R$ of "unstable" terminals, and connectivity requirements {r_{uv}: u,v \in R}, find a minimum size set $S \subseteq M$ of additional points such that the unit-disc graph of $R \cup S$ contains $r_{uv}$ pairwise internally edge-disjoint and $(B \cup S)$-disjoint $uv$-paths for all $u,v \in R$. The case when $r_{uv}=1$ for all $u,v \in R$ is the {\sf Steiner Tree with Minimum Number of Steiner Points} (ST-MSP) problem, and the case $r_{uv} \in \{0,1\}$ is the {\sf Steiner Forest with Minimum Number of Steiner Points} (SF-MSP) problem. Let $\Delta$ be the maximum number of points in a unit ball such that the distance between any two of them is larger than 1. It is known that $\Delta=5$ in $\mathbb{R}^2$ The previous known approximation ratio for {\sf ST-MSP} was $\lfloor (\Delta+1)/2 \rfloor+1+\epsilon$ in an arbitrary normed space \cite{NY}, and $2.5+\epsilon$ in the Euclidean space $\mathbb{R}^2$ \cite{cheng2008relay}. Our approximation ratio for ST-MSP is $1+\ln(\Delta-1)+\epsilon$ in an arbitrary normed space, which in $\mathbb{R}^2$ reduces to $1+\ln 4+\epsilon < 2.3863 +\epsilon$. For SN-MSP with $r_{uv} \in \{0,1,2\}$, we give a simple $\Delta$-approximation algorithm. In particular, for SF-MSP, this improves the previous ratio $2\Delta$.

In Source Location (SL) problems the goal is to select a mini-mum cost source set $S \subseteq V$ such that the connectivity (or flow) $\psi(S,v)$ from $S$ to any node $v$ is at least the demand $d_v$ of $v$. In many SL problems $\psi(S,v)=d_v$ if $v \in S$, namely, the demand of nodes selected to $S$ is completely satisfied. In a node-connectivity variant suggested recently by Fukunaga, every node $v$ gets a "bonus" $p_v \leq d_v$ if it is selected to $S$. Fukunaga showed that for undirected graphs one can achieve ratio $O(k \ln k)$ for his variant, where $k=\max_{v \in V}d_v$ is the maximum demand. We improve this by achieving ratio $\min\{p^*\lnk,k\}\cdot O(\ln (k/q^*))$ for a more general version with node capacities, where $p^*=\max_{v \in V} p_v$ is the maximum bonus and $q^*=\min_{v \in V} q_v$ is the minimum capacity. In particular, for the most natural case $p^*=1$ considered by Fukunaga, we improve the ratio from $O(k \ln k)$ to $O(\ln^2k)$. We also get ratio $O(k)$ for the edge-connectivity version, for which no ratio that depends on $k$ only was known before. To derive these results, we consider a particular case of the Survivable Network (SN) problem when all edges of positive cost form a star. We give ratio $O(\min\{\ln n,\ln^2 k\})$ for this variant, improving over the best ratio known for the general case $O(k^3 \ln n)$ of Chuzhoy and Khanna.

An ordered pair $\hat{S}=(S,S^+)$ of subsets of $V$ is called a {\em biset} if $S \subseteq S^+$; $(V-S^+,V-S)$ is the co-biset of $\hat{S}$. Two bisets $\hat{X},\hat{Y}$ intersect if $X \cap Y \neq \emptyset$ and cross if both $X \cap Y \neq \emptyset$ and $X^+ \cup Y^+ \neq V$. The intersection and the union of two bisets $\hat{X},\hat{Y}$ is defined by $\hat{X} \cap \hat{Y} = (X \cap Y, X^+ \cap Y^+)$ and $\hat{X} \cup \hat{Y} = (X \cup Y,X^+ \cup Y^+)$. A biset-family ${\cal F}$ is crossing (intersecting) if $\hat{X} \cap \hat{Y}, \hat{X} \cup \hat{Y} \in {\cal F}$ for any $\hat{X},\hat{Y} \in {\cal F}$ that cross (intersect). A directed edge covers a biset $\hat{S}$ if it goes from $S$ to $V-S^+$. We consider the problem of covering a crossing biset-family ${\cal F}$ by a minimum-cost set of directed edges. While for intersecting ${\cal F}$, a standard primal-dual algorithm computes an optimal solution, the approximability of the case of crossing ${\cal F}$ is not yet understood, as it includes several NP-hard problems, for which a poly-logarithmic approximation was discovered only recently. Let us say that a biset-family ${\cal F}$ is $k$-regular if $\hat{X} \cap \hat{Y}, \hat{X} \cup \hat{Y} \in {\cal F}$ for any $\hat{X},\hat{Y} \in {\cal F}$ with $|V-(X \cup Y)| \geq k+1$ that intersect. In this paper we obtain an $O(\log |V|)$-approximation algorithm for arbitrary crossing ${\cal F}$; if in addition both ${\cal F}$ and the family of co-bisets of ${\cal F}$ are $k$-regular, our ratios are: $O(\log \frac{|V|}{|V|-k})$ if $|S^+ \setminus S|=k$ for all $\hat{S} \in {\cal F}$, and $O(\frac{|V|}{|V|-k} \log \frac{|V|}{|V|-k})$ if $|S^+ \setminus S| \leq k$ for all $\hat{S} \in {\cal F}$. Using these generic algorithms, we derive approximation algorithms for some network design problems.

Let $G=(V,E)$ be a $k$-edge-connected graph with edge costs $\{c(e):e \in E\}$ and let $1 \leq \ell \leq k-1$. We show by a simple and short proof, that $G$ contains an $\ell$-edge cover $I$ such that: $c(I) \leq \frac{\ell}{k}c(E)$ if $G$ is bipartite, or if $\ell |V|$ is even, or if $|E| \geq \frac{k|V|}{2} +\frac{k}{2\ell}$; otherwise, $c(I) \leq (\frac{\ell}{k}+\frac{1}{k|V|})c(E)$. The particular case $\ell=k-1$ and unit costs already includes a result of Cheriyan and Thurimella, that $G$ contains a $(k-1)$-edge-cover of size $|E|-\lfloor |V|/2 \rfloor$. Using our result, we slightly improve the approximation ratios for the {\sf $k$-Connected Subgraph} problem (the node-connectivity version) with uniform and $\beta$-metric costs. We then consider the dual problem of finding a spanning subgraph of maximum connectivity $k^*$ with a prescribed number of edges. We give an algorithm that computes a $(k^*-1)$-connected subgraph, which is tight, since the problem is NP-hard.

We consider the problem of finding a minimum edge cost subgraph of a graph satisfying both given node-connectivity requirements and degree upper bounds on nodes. We present an iterative rounding algorithm of the biset LP relaxation for this problem. For directed graphs and $k$-out-connectivity requirements from a root, our algorithm computes a solution that is a 2-approximation on the cost, and the degree of each node $v$ in the solution is at most $2b(v) + O(k)$ where $b(v)$ is the degree upper bound on $v$. For undirected graphs and element-connectivity requirements with maximum connectivity requirement $k$, our algorithm computes a solution that is a $4$-approximation on the cost, and the degree of each node $v$ in the solution is at most $4b(v)+O(k)$. These ratios improve the previous $O(\log k)$-approximation on the cost and $O(2^k b(v))$ approximation on the degrees. Our algorithms can be used to improve approximation ratios for other node-connectivity problems such as undirected $k$-out-connectivity, directed and undirected $k$-connectivity, and undirected rooted $k$-connectivity and subset $k$-connectivity., Comment: A preliminary version of this paper appeared in proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012)