A Tight 4.67. Approximation Algorithm for the Multi-Commodity Rent-or-Buy Problem
5,00 €
3,00 €
     
SINTESI
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.
pagine: 16
formato: 17 x 24
ISBN: 978-88-548-0211-7
data pubblicazione: Settembre 2005
editore: Aracne
collana: Dipartimento di Informatica e Sistemistica “Antonio Ruberti” della “Sapienza” Università di Roma | 2005/9
SINTESI
Informativa      Aracneeditrice.it si avvale di cookie, anche di terze parti, per offrirti il migliore servizio possibile. Cliccando 'Accetto' o continuando la navigazione ne acconsenti l'utilizzo. Per saperne di più
Accetto