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. © 2010 Society for Industrial and Applied Mathematics.

Strict cost sharing schemes for steiner forest / Lisa, Fleischer; J., Koenemann; Leonardi, Stefano; G., Schaefer. - In: SIAM JOURNAL ON COMPUTING. - ISSN 0097-5397. - 39:8(2010), pp. 3616-3632. [10.1137/090767108]

Strict cost sharing schemes for steiner forest

LEONARDI, Stefano;
2010

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. © 2010 Society for Industrial and Applied Mathematics.
2010
approximation algorithms; rent-or-buy problems; steiner forests; stochastic optimization; strict cost shares
01 Pubblicazione su rivista::01a Articolo in rivista
Strict cost sharing schemes for steiner forest / Lisa, Fleischer; J., Koenemann; Leonardi, Stefano; G., Schaefer. - In: SIAM JOURNAL ON COMPUTING. - ISSN 0097-5397. - 39:8(2010), pp. 3616-3632. [10.1137/090767108]
File allegati a questo prodotto
File Dimensione Formato  
VE_2010_11573-376449.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 238.67 kB
Formato Adobe PDF
238.67 kB Adobe PDF   Contatta l'autore

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/376449
 Attenzione

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

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