Abstract. Gupta et al. [J. ACM, 54 (2007), article 11] and Gupta, Kumar, and Roughgarden [in Proceedings of the ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 365-372] recently developed an elegant framework for the development of randomized approximation algorithms for rent-or-buy network design problems. The essential building block of this framework is an approximation algorithm for the underlying network design problem that admits a strict cost sharing scheme. Such cost sharing schemes have also proven to be useful in the development of approximation algorithms in the context of two-stage stochastic optimization with recourse. The main contribution of this paper is to show that the Steiner forest problem admits cost shares that are 3-strict and 4-group-strict. As a consequence, we derive surprisingly simple approximation algorithms for the multicommodity rent-or-buy and the multicast rent-or-buy problems with approximation ratios 5 and 6, improving over the previous best approximation ratios of 6.828 and 12.8, respectively. We also show that no approximation ratio better than 4.67 can be achieved using the sampleand-augment framework in combination with the currently best known Steiner forest approximation algorithms. In the context of two-stage stochastic optimization, our result leads to a 6-approximation algorithm for the stochastic Steiner tree problem in the black-box model and a 5-approximation algorithm for the stochastic Steiner forest problem in the independent decision model. 1. Introduction. In the multicommodity rent-or-buy (MRoB) problem we are given an undirected graph G = (V, E) with nonnegative costs c e for all edges e ∈ E, a set of k terminal pairs R = { (s 1 , t 1 ) , . . . , (s k , t k )} ⊆ V × V , a positive demand d i for every terminal pair (s i , t i ) ∈ R, and a parameter M ≥ 1. The goal is to install capacities on the edges of G such that for all (s i , t i ) ∈ R we can simultaneously route d i units of flow from s i to t i . We can either rent capacity on an edge e at cost λ(e) · c(e), where λ(e) is the flow traversing edge e, or buy infinite capacity on edge e at cost M · c(e). Bought edges have no incremental, flow-dependent cost. The overall objective is to find a feasible solution of smallest total cost. The MRoB problem generalizes a number of fundamental optimization problems that are NP-hard. For M = 1 and unit demands, the MRoB problem reduces to the
• Multicommodity rent-or-buy REF .
STRICT COST SHARING SCHEMES FOR STEINER FOREST
SIAM J. Comput.
SIAM J. Comput.
Mathematics Computer Science