Improved approximation for Fractionally Subadditive Network Design

Abstract Recently, Guruganesh et al. [1] proposed the Fractionally Subadditive Network Design (f-SAND) problem. In this problem, we are given a weighted graph G with a special root vertex r together with k subsets of its vertices called scenarios. We need to assign capacities to the edges of G so that for every scenario, the assigned capacities support a unit flow from the root to all vertices in the scenario, simultaneously. The goal is to minimize the total cost of the solution. f-SAND is a fairly natural problem and it generalizes several well-studied problems, such as the Steiner Tree problem. The added interest to this problem stems from the fact that standard tools used for approximating network design problems do not seem to apply to f-SAND. Despite this, Guruganesh et al. conjecture the existence of an algorithm with an approximation ratio bounded by a constant, i.e. independent of k. They make a step towards this goal by giving a 3 2 -approximation algorithm for k = 2 . In this paper, we present an algorithm similar to that of [1] , together with an analysis that not only yields an improved approximation ratio of 4 3 , but is also significantly simpler. We also generalize it to arbitrary k, giving a 2 3 k -approximation. On the negative side, we argue that without additional insights, the techniques used are not likely to produce a constant factor approximation algorithm.