Simple cost sharing schemes for multicommodity rent-or-buy and stochastic steiner tree

Abstract

In the multi-commodity rent-or-buy network design problem (MRoB) we are given a network together with a set of k terminal pairs R = {(s 1,t1},...,(sk,tk)}. The goal is to install capacities on the edges of the network so that a prescribed amount of flow ß can be routed between all terminal pairs si and t i simultaneously. We can either rent capacity on an edge at some cost per unit flow or buy infinite capacity on an edge at some larger fixed cost. The overall objective is to install capacities at a minimum total cost. The version of the stochastic Steiner tree problem (SST) considered here is the Steiner tree problem in the model of two-stage stochastic optimization with recourse. In stage one, there is a known probability distribution on subsets of vertices and we can choose to buy a subset of edges at a given cost. In stage two, a subset of vertices T from the prior known distribution is realized, and additional edges can be bought at a possibly higher cost. The objective is to buy a set of edges in stages one and two so that all vertices in T are connected, and the expected cost is minimized. Gupta et al. (FOCS '03) give a randomized scheme for the MRoB problem that was both used subsequently to improve the approximation ratio for this problem, and extended to yield the best approximation algorithm for SST. One building block of this scheme is a good approximation algorithm for Steiner forests. We present a surprisingly simple 5-approximation algorithm for MRoB and 6-approximation for SST, improving on the best previous guarantees of 6.828 and 12.6, and show that no approximation ratio better than 4.67 can be achieved using the above mentioned randomized scheme in combination with the currently best known Steiner forest approximation algorithms. A key component of our approach are cost shares that are 3-strict for the unmodified primal-dual Steiner forest algorithm. Copyright 2006 ACM.