In the multicommodity rent-or-buy (MROB) network design problem we are given a network together with a set of k terminal pairs (s1,t 1), . . ., (sk, tk). The goal is to provision the network so that a given amount of ow can be shipped between si and ti for all 1 ≤ i ≤ k simultaneously. In order to provision the network one can either rent capacity on edges at some cost per unit of ow, or buy them at some larger fixed cost. Bought edges have no incremental, ow-dependent cost. The overall objective is to minimize the total provisioning cost. Recently, Gupta et al. presented a 12-approximation for the MROB problem. Their algorithm chooses a subset of the terminal pairs in the graph at random and then buys the edges of an approximate Steiner forest for these pairs. This technique has previously been introduced for the single sink rent-or-buy network design problem. In this paper we give a 6.828-approximation for the MROB problem by refining the algorithm of Gupta et al. and simplifying their analysis. The improvement in our paper is based on a more careful adaptation and simplified analysis of the primal-dual algorithm for the Steiner forest problem due to Agrawal, Klein and Ravi. Our result significantly reduces the gap between the single-sink and multi-sink case.

Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy / Becchetti, Luca; Jochen, Koenemann; Leonardi, Stefano; Martin, Pal. - (2005), pp. 375-384. (Intervento presentato al convegno Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms tenutosi a Vancouver; United States nel 23-25 January 2005).

Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy

BECCHETTI, Luca;LEONARDI, Stefano;
2005

Abstract

In the multicommodity rent-or-buy (MROB) network design problem we are given a network together with a set of k terminal pairs (s1,t 1), . . ., (sk, tk). The goal is to provision the network so that a given amount of ow can be shipped between si and ti for all 1 ≤ i ≤ k simultaneously. In order to provision the network one can either rent capacity on edges at some cost per unit of ow, or buy them at some larger fixed cost. Bought edges have no incremental, ow-dependent cost. The overall objective is to minimize the total provisioning cost. Recently, Gupta et al. presented a 12-approximation for the MROB problem. Their algorithm chooses a subset of the terminal pairs in the graph at random and then buys the edges of an approximate Steiner forest for these pairs. This technique has previously been introduced for the single sink rent-or-buy network design problem. In this paper we give a 6.828-approximation for the MROB problem by refining the algorithm of Gupta et al. and simplifying their analysis. The improvement in our paper is based on a more careful adaptation and simplified analysis of the primal-dual algorithm for the Steiner forest problem due to Agrawal, Klein and Ravi. Our result significantly reduces the gap between the single-sink and multi-sink case.
2005
Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
MROB problems; Multicommodity rent or buy (MROB) networks; Primal dual algorithms
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy / Becchetti, Luca; Jochen, Koenemann; Leonardi, Stefano; Martin, Pal. - (2005), pp. 375-384. (Intervento presentato al convegno Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms tenutosi a Vancouver; United States nel 23-25 January 2005).
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/235429
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 6
social impact