Search

In the Tree Augmentation problem the goal is to augment a tree T by a minimum size edge set F from a given edge set E such that T ∪ F is 2-edge-connected. The best approximation ratio known for the problem is 1.5. In the more general Weighted Tree Augmentation problem, F should be of minimum weight. Weighted Tree Augmentation admits several 2-approximation algorithms w.r.t. the standard cut-LP relaxation. Improving this natural ratio is a major open problem, and resolving it may have implications on other network design problems. It seems that achieving this goal requires finding an LP-relaxation with integrality gap better than 2, which is an old open problem even for Tree Augmentation . In this paper we introduce two different LP-relaxations, and for each of them give a simple combinatorial algorithm that computes a feasible solution for Tree Augmentation of size at most 1.75 times the optimal LP value. [ABSTRACT FROM AUTHOR]

In the Fixed Cost k-Flow problem, we are given a graph G = ( V, E) with edge-capacities { u∣ e ∈ E} and edge-costs { c∣ e ∈ E}, source-sink pair s, t ∈ V, and an integer k. The goal is to find a minimum cost subgraph H of G such that the minimum capacity of an st-cut in H is at least k. By an approximation-preserving reduction from Group Steiner Tree problem to Fixed Cost k-Flow, we obtain the first polylogarithmic lower bound for the problem; this also implies the first non-constant lower bounds for the Capacitated Steiner Network and Capacitated Multicommodity Flow problems. We then consider two special cases of Fixed Cost k-Flow. In the Bipartite Fixed-Cost k-Flow problem, we are given a bipartite graph G = ( A ∪ B, E) and an integer k > 0. The goal is to find a node subset S ⊆ A ∪ B of minimum size | S| such G has k pairwise edge-disjoint paths between S ∩ A and S ∩ B. We give an $O(\sqrt {k\log k})$ approximation for this problem. We also show that we can compute a solution of optimum size with Ω( k/polylog( n)) paths, where n = | A| + | B|. In the Generalized-P2P problem we are given an undirected graph G = ( V, E) with edge-costs and integer charges { b : v ∈ V}. The goal is to find a minimum-cost spanning subgraph H of G such that every connected component of H has non-negative charge. This problem originated in a practical project for shift design []. Besides that, it generalizes many problems such as Steiner Forest, k-Steiner Tree, and Point to Point Connection. We give a logarithmic approximation algorithm for this problem. Finally, we consider a related problem called Connected Rent or Buy Multicommodity Flow and give a log n approximation scheme for it using Group Steiner Tree techniques. [ABSTRACT FROM AUTHOR]

The Tree Augmentation Problem (TAP) is as follows: given a connected graph G = (V, ε) and an edge set E on V, find a minimum size subset of edges F ⊆ E such that (V, E ∪ F) is 2-edge-connected. In the conference version [Even et al. 2001] 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. The first part [Even et al. 2009] only proved ratio 1.8. An attempt to simplify the second part produced an error in Even et al. [2011]. 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. [ABSTRACT FROM AUTHOR]

We study two-stage robust variants of combinatorial optimization problems on undirected graphs, like Steiner tree, Steiner forest, and uncapacitated facility location. Robust optimization problems, previously studied by Dhamdhere et al. (Proc. of 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), pp. 367-378, ), Golovin et al. (Proc. of the 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS), ), and Feige et al. (Proc. of the 12th International Integer Programming and Combinatorial Optimization Conference, pp. 439-453, ), are two-stage planning problems in which the requirements are revealed after some decisions are taken in Stage 1. One has to then complete the solution, at a higher cost, to meet the given requirements. In the robust k-Steiner tree problem, for example, one buys some edges in Stage 1. Then k terminals are revealed in Stage 2 and one has to buy more edges, at a higher cost, to complete the Stage 1 solution to build a Steiner tree on these terminals. The objective is to minimize the total cost under the worst-case scenario. In this paper, we focus on the case of exponentially many scenarios given implicitly. A scenario consists of any subset of k terminals (for k-Steiner tree), or any subset of k terminal-pairs (for k-Steiner forest), or any subset of k clients (for facility location). Feige et al. (Proc. of the 12th International Integer Programming and Combinatorial Optimization Conference, pp. 439-453, ) give an LP-based general framework for approximation algorithms for a class of two stage robust problems. Their framework cannot be used for network design problems like k-Steiner tree (see later elaboration). Their framework can be used for the robust facility location problem, but gives only a logarithmic approximation. We present the first constant-factor approximation algorithms for the robust k-Steiner tree (with exponential number of scenarios) and robust uncapacitated facility location problems. Our algorithms are combinatorial and are based on guessing the optimum cost and clustering to aggregate nearby vertices. For the robust k-Steiner forest problem on trees and with uniform multiplicative increase factor for Stage 2 (also known as inflation), we present a constant approximation. We show APX-hardness of the robust min-cut problem (even with singleton-set scenarios), resolving an open question of (Dhamdhere et al. in Proc. of 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), pp. 367-378, ) and (Golovin et al. in Proc. of the 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS), ). [ABSTRACT FROM AUTHOR]

Abstract: We consider the k-Directed Steiner Forest (k-DSF) problem: Given a directed graph with edge costs, a collection of ordered node pairs, and an integer , find a minimum cost subgraph H of G that contains an st-path for (at least) k pairs . When , we get the Directed Steiner Forest (DSF) problem. The best known approximation ratios for these problems are: for k-DSF by Charikar et al. (1999) , and for DSF by Chekuri et al. (2008) . Our main result is achieving the first sub-linear in terms of approximation ratio for DSF. Specifically, we give an -approximation scheme for DSF. For k-DSF we give a simple greedy -approximation algorithm. This improves upon the best known ratio by Charikar et al. (1999) , and (almost) matches, in terms of k, the best ratio known for the undirected variant (Gupta et al., 2010 ). This algorithm uses a new structure called start-junction tree which may be of independent interest. [Copyright &y& Elsevier]

Abstract: We study several multi-criteria undirected network design problems with node costs and lengths. All these problems are related to the Multicommodity Buy at Bulk (MBB) problem in which we are given a graph , demands , and a family of subadditive cost functions. For every we seek to send flow units from to , so that is minimized, where is the total amount of flow through . It is shown in Andrews and Zhang (2002) that with a loss of in the ratio, we may assume that each -flow is unsplittable, namely, uses only one path. In the Multicommodity Cost–Distance (MCD) problem we are also given lengths , and seek a subgraph of that minimizes , where is the minimum -length of an -path in . The approximability of these two problems is equivalent up to a factor . We give an -approximation algorithm for both problems for the case of the demands polynomial in . The previously best known approximation ratio for these problems was (Chekuri et al., 2006, 2007) . We also consider the Maximum Covering Tree (MaxCT) problem which is closely related to MBB: given a graph , costs , profits , and a bound , find a subtree of with and maximum. The best known approximation algorithm for MaxCT (Moss and Rabani, 2001) computes a tree with and . We provide the first nontrivial lower bound on approximation by proving that the problem admits no better than approximation assuming . This holds true even if the solution is allowed to violate the budget by a constant , as was done in with . Our result disproves a conjecture of . Another problem related to MBB is the Shallow Light Steiner Tree (SLST) problem, in which we are given a graph , costs , lengths , a set of terminals, and a bound . The goal is to find a subtree of containing with and minimum. We give an algorithm that computes a tree with and . Previously, a polylogarithmic bicriteria approximation was known only for the case of edge costs and edge lengths. [Copyright &y& Elsevier]

We study approximation algorithms, integrality gaps, and hardness of approximation of two problems related to cycles of "small" length k in a given (undirected) graph. The instance for these problems consists of a graph G = (V,E) and an integer k. The k-Cycle Transversal problem is to find a minimum edge subset of E that intersects every k-cycle. The k-Cycle-Free Subgraph problem is to find a maximum edge subset of E without k-cycles. Our main result is for the k-Cycle-Free Subgraph problem with even values of k. For any k = 2r, we give an Ω(n-1/r + 1/r(2r-1)-ϵ )-approximation scheme with running time (1/ϵ)O(1/ϵ)poly(n), where n = ∣V∣ is the number of vertices in the graph. This improves upon the ratio 9 (n-1/r) that can be deduced from extremal graph theory. In particular, for k = 4 the improvement is from Ω(n-1/2) to Ω(n-1/3-ϵ). Our additional result is for odd k. The 3-Cycle Transversal problem (covering all triangles) was studied by Krivelevich [Discrete Math., 142 (1995), pp. 281-286], who presented an LP-based 2-approximation algorithm. We show that k-Cycle Transversal admits a (k - 1)-approximation algorithm, which extends to any odd k the result that Krivelevich proved for k = 3. Based on this, for odd k we give an algorithm for k-Cycle-Free Subgraph with ratio k-1/2k-3 = 1/2 + 1/4k-6 ; this improves upon the trivial ratio of 1/2. For k = 3, the integrality gap of the underlying LP was posed as an open problem in the work of Krivelevich. We resolve this problem by showing a sequence of graphs with integrality gap approaching 2. In addition, we show that if k-Cycle Transversal admits a (2 - ϵ)-approximation algorithm, then so does the Vertex-Cover problem; thus improving the ratio 2 is unlikely. Similar results are shown for the problem of covering cycles of length ≤ k or finding a maximum subgraph without cycles of length ≤ k (i.e., with girth > k). [ABSTRACT FROM AUTHOR]

We present a 1.8-approximation algorithm for the following NP-hard problem: Given a connected graph G = (V, Ɛ) and an edge set E on V disjoint to E, find a minimum-size subset of edges F ⊆ E such that (V, Ɛ ∪ F) is 2-edge-connected. Our result improves and significantly simplifies the approximation algorithm with ratio 1.875 + ϵ of Nagamochi. [ABSTRACT FROM AUTHOR]

Abstract: The S-connectivity of in a graph G is the maximum number of uv-paths that no two of them have an edge or a node in in common. The corresponding Connectivity Augmentation () problem is: given a graph , , and requirements on , find a minimum size set F of new edges (any edge is allowed) so that for all . Extensively studied particular choices of S are the edge- (when ) and the node- (when ). A. Frank gave a polynomial algorithm for undirected edge- and observed that the directed case even with rooted -requirements is at least as hard as the Set-Cover problem (in rooted requirements there is so that if then: for directed graphs, and or for undirected graphs). Both directed and undirected node- have approximation threshold . The only polylogarithmic approximation ratio known for was for rooted requirements—, where . No nontrivial approximation algorithms were known for directed even for , nor for undirected with S arbitrary. We give an approximation algorithm for the general case that matches the known approximation thresholds. For both directed and undirected with arbitrary requirements our approximation ratio is: for arbitrary, and for . [Copyright &y& Elsevier]

We consider a general class of scheduling problems where a set of conflicting jobs needs to be scheduled (preemptively or nonpreemptively) on a set of machines so as to minimize the weighted sum of completion times. The conflicts among jobs are formed as an arbitrary conflict graph. Building on the framework of Queyranne and Sviridenko [2002b], we present a general technique for reducing the weighted sum of completion-times problem to the classical makespan minimization problem. Using this technique, we improve the best-known results for scheduling conflicting jobs with the min-sum objective, on several fundamental classes of graphs, including line graphs, (k +1)-claw-free graphs, and perfect graphs. In particular, we obtain the first constant-factor approximation ratio for nonpreemptive scheduling on interval graphs. We also improve the results of Kim [2003] for scheduling jobs on line graphs and for resource-constrained scheduling. [ABSTRACT FROM AUTHOR]

We present two new approximation algorithms for the problem of finding a k-node connected spanning subgraph (directed or undirected) of minimum cost. The best known approximation guarantees for this problem were $O(\min \{k,\frac{n}{\sqrt{n-k}}\})$ for both directed and undirected graphs, and $O(\ln k)$ for undirected graphs with $n \geq 6k^2$, where $n$ is the number of nodes in the input graph. Our first algorithm has approximation ratio $O(\frac{n}{n-k}\ln^2 k)$, which is $O(\ln^2 k)$ except for very large values of $k$, namely, $k=n-o(n)$. This algorithm is based on a new result on $\ell$-connected $p$-critical graphs, which is of independent interest in the context of graph theory. Our second algorithm uses the primal-dual method and has approximation ratio $O(\sqrt{n} \ln k)$ for all values of $n,k$. Combining these two gives an algorithm with approximation ratio $O(\ln k \cdot \min \{\sqrt{k},\frac{n}{n-k} \ln k\})$, which asymptotically improves the best known approximation guarantee for directed graphs for all values of $n,k$, and for undirected graphs for $k>\sqrt{n/6}$. Moreover, this is the first algorithm that has an approximation guarantee better than $\Theta(k)$ for all values of $n,k$. Our approximation ratio also provides an upper bound on the integrality gap of the standard LP-relaxation. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we consider the checkpoint problem. The input consists of an undirected graph , a set of source–destination pairs , and a collection of paths connecting the pairs. A feasible solution is a multicut , namely, a set of edges whose removal disconnects every source–destination pair. For each we define . In the sum checkpoint (SCP) problem the goal is to minimize , while in the maximum checkpoint (MCP) problem the goal is to minimize . These problems have several natural applications, e.g., in urban transportation and network security. In a sense, they combine the multicut problem and the minimum membership set cover problem. For the sum objective we show that weighted SCP is equivalent, with respect to approximability, to undirected multicut. Thus there exists an approximation for SCP in general graphs. Our current approximability results for the max objective have a wide gap: we provide an approximation factor of for MCP and a hardness of 2 under the assumption . The hardness holds for trees. This solves an open problem of Nelson (2009) . We complement the lower bound by an almost matching upper bound with an asymptotic approximation factor of 2. On trees with all having an ancestor–descendant relation, we give a combinatorial exact algorithm. Besides the algorithm being combinatorial, its running time improves by many orders of magnitude the LP algorithm that follows from total unimodularity. Finally, we show strong hardness for the well-known problem of finding a path with minimum forbidden pairs, which in a sense can be considered the dual to the checkpoint problem. Despite various works on this problem, hardness of approximation was not known prior to this work. We show that the problem cannot be approximated within for some constant , unless . This is the strongest type of hardness possible. It carries over to directed acyclic graphs and is a huge improvement over the plain -hardness of Gabow [H.N. Gabow, Finding paths and cycles of superpolylogarithmic length, SIAM J. Comput. 36 (6) (2007) 1648–1671]. [Copyright &y& Elsevier]

Abstract: In the group Steiner problem we are given an edge-weighted graph and m subsets of vertices . Each subset is called a group and the vertices in are called terminals. It is required to find a minimum weight tree that contains at least one terminal from every group. We present a poly-logarithmic ratio approximation for this problem when the input graph is a tree. Our algorithm is a recursive greedy algorithm adapted from the greedy algorithm for the directed Steiner tree problem [Approximating the weight of shallow Steiner trees, Discrete Appl. Math. 93 (1999) 265–285, Approximation algorithms for directed Steiner problems, J. Algorithms 33 (1999) 73–91]. This is in contrast to earlier algorithms that are based on rounding a linear programming based relaxation for the problem [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. Algorithms 37 (2000) 66–84, preliminary version in Proceedings of SODA, 1998 pp. 253–259, On directed Steiner trees, Proceedings of SODA, 2002, pp. 59–63]. We answer in positive a question posed in [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. Algorithms 37 (2000) 66–84, preliminary version in Proceedings of SODA, 1998 pp. 253–259] on whether there exist good approximation algorithms for the group Steiner problem that are not based on rounding linear programs. For every fixed constant , our algorithm gives an approximation in polynomial time. Approximation algorithms for trees can be extended to arbitrary undirected graphs by probabilistically approximating the graph by a tree. This results in an additional multiplicative factor of in the approximation ratio, where is the number of vertices in the graph. The approximation ratio of our algorithm on trees is slightly worse than the ratio of provided by the LP based approaches. [Copyright &y& Elsevier]