Seminario Interdipartimentale di Algoritmica  

Monday, July 4, 2005, 12:00 noon
A Tight 4.66-Approximation for Multicommodity Rent-or-Buy
Guido Schaefer, Università di Roma "La Sapienza"

DI - Department of Computer Science
Seminar Room, third floor

Abstract:

In the multicommodity rent-or-buy network design problem (MRoB) we are given a network together with k terminal pairs (s_i, t_i). The goal is to install capacities on the edges of the network so that a prescribed amount of flow f_i can be routed between all terminal pairs s_i 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. 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.82-approximation algorithm is due to Becchetti et al. (SODA '05). We present a surprisingly simple primal-dual 4.66-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 approximation algorithms.

Joint work with:

* Lisa Fleischer, IBM Watson, USA
* Jochen Koenemann, University of Waterloo, Canada
* Stefano Leonardi, University of Rome "La Sapienza", Italy