Search

In the Steiner k-Forest problem we are given an edge weighted graph, a collection D of node pairs, and an integer k ≤ |D|. The goal is to find a minimum cost subgraph that connects at least kpairs. The best known ratio for this problem is min{O(√n), O(√k)} [8]. In [8] it is also shown that ratio ρ for Steiner k-Forest implies ratio O(ρ · log2 n) for the Dial-a-Ride problem: given an edge weighted graph and a set of items with a source and a destination each, find a minimum length tour to move each object from its source to destination, but carrying at most k objects at a time. The only other algorithm known for Dial-a-Ride, besides the one resulting from [8], has ratio O(√n) [4]. We obtain ratio n0.448 for Steiner k-Forest and Dial-a-Ride with unit weights, breaking the O(√n) ratio barrier for this natural special case. We also show that if the maximum weight of an edge is O(nϵ), then one can achieve ratio O(n(1+ϵ)0.448), which is less than √n if ϵ is small enough. To prove our main result we consider the following generalization of the Minimum k-Edge Subgraph (Mk-ES) problem, which we call Min-Cost-Edge-Profit Subgraph (MC-EPS): Given a graph G = (V, E) with edge-profits p = {pe : e ∈ E} and node-costs c = {cv : v ∈ V }, and a lower profit bound , find a minimum node-cost subgraph of G of edge profit at least . The Mk-ES problem is a special case of MC-EPS with unit node costs and unit edge profits. The currently best known ratio for Mk-ES is n3−2√2+ϵ(note that 3 − 2√2 < 0.1716) [5]. We extend this ratio to MC-EPS for arbitrary node weights and edge profits that are polynomial in n, which may be of independent interest. [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 give approximation algorithms for the Survivable Network problem. The input consists of a graph G = (V, E) with edge/node-costs, a node subset S ⊆ V, and connectivity requirements {r(s, t) : s, t ε T ⊆ V}. The goal is to find a minimum cost subgraph H of G that for all s, t ε T contains r(s, t) pairwise edge-disjoint st-paths such that no two of them have a node in S \ {s, t} in common. Three extensively studied particular cases are: Edge-Connectivity Survivable Network (S = Ø), Node-Connectivity Survivable Network (S = V), and Element-Connectivity Survivable Network (r(s, t) = 0 whenever s ε S or t ε S). Let k = maxs,tεT r(s, t). In Rooted Survivable Network, there is s ε T such that r(u, t) = 0 for all u ≠ s, and in the Subset k-Connected Subgraph problem r(s, t) = k for all s, t ε T. For edge-costs, our ratios are O(klog k) for Rooted Survivable Network and O(k2 log k) for Subset k- Connected Subgraph. This improves the previous ratio O(k2 log n), and for constant values of k settles the approximability of these problems to a constant. For node-costs, our ratios are as follows. O(klog |T|) for Element-Connectivity Survivable Network, matching the best known ratio for Edge- Connectivity Survivable Network. O(k2 log |T|) for Rooted Survivable Network and O(k3 log |T|) for Subset k-Connected Subgraph, improving the ratio O(k8 log2 |T|). O(k4 log2 |T|) for Survivable Network; this is the first nontrivial approximation algorithm for the node-costs version of the problem. [ABSTRACT FROM AUTHOR]

In the Steiner Network problem, we are given a graph G with edge-costs and connectivity requirements ruv between node pairs u, v. The goal is to find a minimum-cost subgraph H of G that contains ruv edge-disjoint paths for all u, v ε V. In Prize-Collecting Steiner Network problems, we do not need to satisfy all requirements, but are given a penalty function for violating the connectivity requirements, and the goal is to find a subgraph H that minimizes the cost plus the penalty. The case when ruv ε {0, 1} is the classic Prize-Collecting Steiner Forest problem. In this article, we present a novel linear programming relaxation for the Prize-Collecting Steiner Network problem, and by rounding it, obtain the first constant-factor approximation algorithm for submodular and monotone nondecreasing penalty functions. In particular, our setting includes all-or-nothing penalty functions, which charge the penalty even if the connectivity requirement is slightly violated; this resolves an open question posed by Nagarajan et al. [2008]. We further generalize our results for element-connectivity and node-connectivity. [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]

The cycle packing number ve(G) of a graph G is the maximum number of pairwise edge-disjoint cycles in G. Computing ve(G) is an NP-hard problem. We present approximation algorithms for computing ve(G) in both undirected and directed graphs. In the undirected case we analyze a variant of the modified greedy algorithm suggested by Caprara et al. [2003] and showthat it has approximation ratio Θ(√log n), where n = ∣V(G)∣. This improves upon the previous O(log n) upper bound for the approximation ratio of this algorithm. In the directed case we present √n-approximation algorithm. Finally, we give an O(n2/3)-approximation algorithm for the problem of finding a maximum number of edge-disjoint cycles that intersect a specified subset S of vertices. We also study generalizations of these problems. Our approximation ratios are the currently best-known ones and, in addition, provide upper bounds on the integrality gap of standard LP-relaxations of these problems. In addition, we give lower bounds for the integrality gap and approximability of ve(G) in directed graphs. Specifically, we prove a lower bound of Ω( log n/log log n ) for the integrality gap of edge-disjoint cycle packing. We also show that it is quasi-NP-hard to approximate ve(G) within a factor of O(log1-ϵ n) for any constant ϵ > 0. This improves upon the previously known APX-hardness result for this problem. [ABSTRACT FROM AUTHOR]