In this paper, we study a survivable network design problem on directed graphs, 2-Connected Directed Steiner Tree (2-DST): given an @math -vertex weighted directed graph, a root @math , and a set of @math terminals @math , find a min-cost subgraph @math that has two edge vertex disjoint paths from @math to any @math . 2-DST is a natural generalization of the classical Directed Steiner Tree problem (DST), where we have an additional requirement that the network must tolerate one failure. No non-trivial approximation is known for 2-DST. This was left as an open problem by , [SODA'09; JCSS] and has then been studied by [SODA'12; TALG] and Laekhanukit SODA'14]. However, no positive result was known except for the special case of a @math -shallow instance [Laekhanukit, ICALP'16]. We present an @math approximation algorithm for 2-DST that runs in time @math , for any @math . This implies a polynomial-time @math approximation for any constant @math , and a poly-logarithmic approximation running in quasi-polynomial time. We remark that this is essentially the best-known even for the classical DST, and the latter problem is @math -hard to approximate [Halperin and Krauthgamer, STOC'03]. As a by product, we obtain an algorithm with the same approximation guarantee for the @math -Connected Directed Steiner Subgraph problem, where the goal is to find a min-cost subgraph such that every pair of terminals are @math -edge vertex connected.
As already mentioned, survivable network design is well studied in undirected (weighted) graphs. First, consider the edge connectivity version. The earliest work is initiated in early 80's by Frederickson and J ' a J ' a @cite_22 , where the authors studied the 2-Edge Connected Subgraph problem in both directed and undirected graphs. In the most general form of the problem, also known as the problem, we are given non-negative integer requirements @math for all pairs of vertices @math , and the goal is to find a min-cost subgraph that has @math edge-disjoint paths between @math and @math . Jain @cite_0 devised a @math -approximation algorithm for this problem. We remark that @math is the best known approximation factor even for @math @cite_39 , which is known as the problem. The classical problem is a special case of Steiner forest where all pairs share one vertex. Here the best known approximation factor is @math due to the work of Byrka et al. @cite_27 .
@cite_0 @cite_27 @cite_22 @cite_39
2172955861 1976584101 2051699458 2011823863
The Steiner tree problem is one of the most fundamental NP-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was improved from 2 to 1.55 [Robins and Zelikovsky 2005]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP relaxation of Steiner tree with integrality gap smaller than 2 [Rajagopalan and Vazirani 1999]. In this article we present an LP-based approximation algorithm for Steiner tree with an improved approximation factor. Our algorithm is based on a, seemingly novel, iterative randomized rounding technique. We consider an LP relaxation of the problem, which is based on the notion of directed components. We sample one component with probability proportional to the value of the associated variable in a fractional solution: the sampled component is contracted and the LP is updated consequently. We iterate this process until all terminals are connected. Our algorithm delivers a solution of cost at most ln(4) + e As a by-product of our analysis, we show that the integrality gap of our LP is at most 1.55, hence answering the mentioned open question. Graph augmentation problems on a weighted graph involve determining a minimum-cost set of edges to add to a graph to satisfy a specified property, such as biconnectivity, bridge-connectivity or str... We give the first approximation algorithm for the generalized network Steiner problem, a problem in network design. An instance consists of a network with link-costs and, for each pair @math of nodes, an edge-connectivity requirement @math . The goal is to find a minimum-cost network using the available links and satisfying the requirements. Our algorithm outputs a solution whose cost is within @math of optimal, where @math is the highest requirement value. In the course of proving the performance guarantee, we prove a combinatorial min-max approximate equality relating minimum-cost networks to maximum packings of certain kinds of cuts. As a consequence of the proof of this theorem, we obtain an approximation algorithm for optimally packing these cuts; we show that this algorithm has application to estimating the reliability of a probabilistic network.