A Tight 4.67. Approximation Algorithm for the Multi-Commodity Rent-or-Buy Problem

Area 09 – Ingegneria industriale e dell'informazione

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 = {(s1,t1), . . . , (sk,tk)}. The goal is to install capacities on the edges of the network so that a prescribed amount of flow fi can be routed between all terminal pairs si and ti 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.Gupta et al. (FOCS ’03) gave a randomized scheme for the MRoB problem that has been used subsequently to improve the approximation ratio for this problem. The currently best known 6.828-approximation algorithm is due to Becchetti et al. (SODA ’05).We present a surprisingly simple primal-dual 4.67-approximation algorithm and show that this result is tight; that is, no better approximation ratio can be achieved using the above mentioned randomized scheme in combination with the currently best known Steiner forest approximation algorithm.

SINTESI