The minimum-weight @math -edge-connected spanning subgraph (2-ECSS) problem is a natural generalization of the well-studied minimum-weight spanning tree (MST) problem, and it has received considerable attention in the area of network design. The latter problem asks for a minimum-weight subgraph with an edge connectivity of @math between each pair of vertices while the former strengthens this edge-connectivity requirement to @math . Despite this resemblance, the 2-ECSS problem is considerably more complex than MST. While MST admits a linear-time centralized exact algorithm, 2-ECSS is NP-hard and the best known centralized approximation algorithm for it (that runs in polynomial time) gives a @math -approximation. In this paper, we give a deterministic distributed algorithm with round complexity of @math that computes a @math -approximation of 2-ECSS, for any constant @math . Up to logarithmic factors, this complexity matches the @math lower bound that can be derived from Das [STOC'11], as shown by Censor-Hillel and Dory [OPODIS'17]. Our result is the first distributed constant approximation for 2-ECSS in the nearly optimal time and it improves on a recent randomized algorithm of Dory [PODC'18], which achieved an @math -approximation in @math rounds. We also present an alternative algorithm for @math -approximation, whose round complexity is linear in the low-congestion shortcut parameter of the network, following a framework introduced by Ghaffari and Haeupler [SODA'16]. This algorithm has round complexity @math in worst-case networks but it provably runs much faster in many well-behaved graph families of interest. For instance, it runs in @math time in planar networks and those with bounded genus, bounded path-width or bounded tree-width.
The problem of computing a minimum 2-ECSS is known to be NP-hard, by a reduction from the Hamiltonian cycle problem @cite_26 . This already shows that 2-ECSS is much harder than the closely related problem of MST, which admits a linear-time (randomized) centralized exact algorithm @cite_8 . The best known centralized (polynomial-time) approximation algorithms for 2-ECSS give a @math -approximation @cite_25 @cite_13 . These algorithms also give a @math -approximation for the more general minimum-weight @math -edge-connected spanning subgraph ( @math -ECSS). If all edge-weights are equal (i.e., in the unweighted case), then the best known approximation factors become @math and @math , respectively, for 2-ECSS @cite_2 and @math -ECSS @cite_31 .
@cite_26 @cite_8 @cite_2 @cite_31 @cite_13 @cite_25
1605196620 2138304862 1999799345 2083162966 2092113566
We consider the distributed construction of a minimum weight 2- edge-connected spanning subgraph (2-ECSS) of a given weighted or unweighted graph. A 2-ECSS of a graph is a subgraph that, for each pair of vertices, contains at least two edge-disjoint paths connecting these vertices. The problem of finding a minimum weight 2-ECSS is NP-hard and a natural extension of the distributed MST construction problem, one of the most fundamental problems in the area of distributed computation. We present a distributed 3 2-approximation algorithm for the unweighted 2-ECSS construction problem that requires O(n) communication rounds and O(m) messages. Moreover, we present a distributed 3-approximation algorithm for the weighted 2-ECSS construction problem that requires O(nlogn) communication rounds and O(nlog2 n+m) messages. An efficient heuristic is presented for the problem of finding a minimum-size k-connected spanning subgraph of a given (undirected or directed) graph G=(V,E). There are four versions of the problem, depending on whether G is undirected or directed, and whether the spanning subgraph is required to be k-node connected (k-NCSS) or k-edge connected (k-ECSS). The approximation guarantees are as follows: min-size k-NCSS of an undirected graph 1+[1 k], min-size k-NCSS of a directed graph 1+[1 k], min-size k-ECSS of an undirected graph 1+[7 k], & min-size k-ECSS of a directed graph 1+[4 spl radic k]. The heuristic is based on a subroutine for the degree-constrained subgraph (b-matching) problem. It is simple, deterministic, and runs in time O(k|E| sup 2 ). For undirected graphs and k=2, a (deterministic) parallel NC version of the heuristic finds a 2-node connected (or a-edge connected) spanning subgraph whose size is within a factor of (1.5+ spl epsiv ) of minimum, where spl epsiv >0 is a constant. The smallest k-ECSS problem is, given a graph along with an integer k, find a spanning subgraph that is k-edge connected and contains the fewest possible number of edges. We examine a natural approximation algorithm based on rounding an LP solution. A tight bound on the approximation ratio is 1 + 3-k for undirected graphs with k > 1 odd, 1 + 2-k for undirected graphs with k even, and 1 + 2-k for directed graphs with k arbitrary. Using iterated rounding improves the first upper bound to 1 + 2-k. On the hardness side we show that for some absolute constant c > 0, for any integer k  2 (k  1), a polynomial-time algorithm approximating the smallest k-ECSS on undirected (directed) multigraphs to within ratio 1 + c-k would imply P = NP.  2008 Wiley Periodicals, Inc. NETWORKS, 2009 We give a 7.18-approximation algorithm for the minimum latency problem that uses only @math calls to the prize-collecting Steiner tree (PCST) subroutine of Goemans and Williamson. This improves the previous best algorithms in both performance guarantee and running time. A previous algorithm of Goemans and Kleinberg for the minimum latency problem requires an approximation algorithm for the @math -minimum spanning tree ( @math -MST) problem which is called as a black box for each value of @math . Their algorithm can achieve an approximation factor of 10.77 while making @math PCST calls, a factor of 8.98 using @math PCST calls, or a factor of @math using @math PCST calls, via the @math -MST algorithms of Garg, Arya and Ramesh, and Arora and Karakostas, respectively. Here @math denotes the number of nodes in the instance, and @math is the largest edge cost in the input. In all cases, the running time is dominated by the PCST calls. Since the PCST subroutine can be implemented to run in @math time, the overall running time of our algorithm is @math . We also give a faster randomized version of our algorithm that achieves the same approximation guarantee in expectation, but uses only @math PCST calls, and derandomize it to obtain a deterministic algorithm with factor @math , using @math PCST calls. The basic idea for our improvement is that we do not treat the @math -MST algorithm as a black box. This allows us to take advantage of some special situations in which the PCST subroutine delivers a 2-approximate @math -MST. We are able to obtain the same approximation ratio that would be given by Goemans and Kleinberg if we had access to 2-approximate @math -MSTs for all values of @math , even We present a general approximation technique for a large class of graph problems. Our technique mostly applies to problems of covering, at minimum cost, the vertices of a graph with trees, cycles or paths satisfying certain requirements. In particular, many basic combinatorial optimization problems fit in this framework, including the shortest path, minimum-cost spanning tree, minimum-weight perfect matching, traveling salesman and Steiner tree problems. Our technique produces approximation algorithms that run in @math time and come within a factor of 2 of optimal for most of these problems. For instance, we obtain a 2-approximation algorithm for the minimum-weight perfect matching problem under the triangle inequality. Our running time of @math time compares favorably with the best strongly polynomial exact algorithms running in @math time for dense graphs. A similar result is obtained for the 2-matching problem and its variants. We also derive the first approximation algorithms for many NP-complete problems, including the non-fixed point-to-point connection problem, the exact path partitioning problem and complex location-design problems. Moreover, for the prize-collecting traveling salesman or Steiner tree problems, we obtain 2-approximation algorithms, therefore improving the previously best-known performance guarantees of 2.5 and 3, respectively [Math. Programming, 59 (1993), pp. 413--420]. We consider the following generalization of the binary search problem. A search strategy is required to locate an unknown target node @math in a given tree @math . Upon querying a node @math of the tree, the strategy receives as a reply an indication of the connected component of @math containing the target @math . The cost of querying each node is given by a known non-negative weight function, and the considered objective is to minimize the total query cost for a worst-case choice of the target. Designing an optimal strategy for a weighted tree search instance is known to be strongly NP-hard, in contrast to the unweighted variant of the problem which can be solved optimally in linear time. Here, we show that weighted tree search admits a quasi-polynomial time approximation scheme: for any @math , there exists a @math -approximation strategy with a computation time of @math . Thus, the problem is not APX-hard, unless @math . By applying a generic reduction, we obtain as a corollary that the studied problem admits a polynomial-time @math -approximation. This improves previous @math -approximation approaches, where the @math -notation disregards @math -factors.