Search

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 θ 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 ⊆ V of terminals, and thresholds { t u e , t v e } for each uv -edge e ∈ E. The goal is to find an assignment a = { a v : v ∈ V } to the nodes minimizing ∑ v ∈ V a v , such that the edge set E a = { e = u v : a u ≥ t u e , a v ≥ t v e } activated by a covers R. We obtain ratio 1 + max x ≥ 1 ⁡ ln ⁡ x 1 + x / θ ≈ ln ⁡ θ − ln ⁡ ln ⁡ θ for the problem, where θ ≤ max e ∈ E ⁡ max ⁡ { t u e , t v e } min ⁡ { t u e , t v e } 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 the same ratio for the above variant of Facility Location. If for each facility all service costs are identical then we show a better ratio 1 + max k ∈ N ⁡ H k − 1 1 + k / θ , where H k = ∑ i = 1 k 1 / i. For the Min-Power Edge-Cover problem we improve the ratio 1.406 of [4] (achieved by iterative randomized rounding) to 1.2785. For unit thresholds we improve the ratio 73 / 60 ≈ 1.217 of [4] to 1555 1347 ≈ 1.155. [ABSTRACT FROM AUTHOR]

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]

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]

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]

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]