In the hose model we are given upper bounds b(u)(-)/b(u)(+) on the amount of traffic entering/leaving a node. We show that when Sigma(u epsilon v)b(u)(+)=Sigma(nu epsilon v)b(u)(-), designing a minimum cost tree network is easy and the cost of an optimal tree reservation is within a factor of three of the cost of any reservation. (c) 2005 Elsevier B.V. All rights reserved.

Italiano, G.f., Leonardi, S., Oriolo, G. (2006). Design of trees in the hose model: The balanced case. OPERATIONS RESEARCH LETTERS, 34(6), 601-606 [10.1016/j.orl.2005.09.005].

Design of trees in the hose model: The balanced case

ITALIANO, GIUSEPPE FRANCESCO;ORIOLO, GIANPAOLO
2006-01-01

Abstract

In the hose model we are given upper bounds b(u)(-)/b(u)(+) on the amount of traffic entering/leaving a node. We show that when Sigma(u epsilon v)b(u)(+)=Sigma(nu epsilon v)b(u)(-), designing a minimum cost tree network is easy and the cost of an optimal tree reservation is within a factor of three of the cost of any reservation. (c) 2005 Elsevier B.V. All rights reserved.
2006
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI
English
Con Impact Factor ISI
Approximation algorithms; Hose model; Network design
Italiano, G.f., Leonardi, S., Oriolo, G. (2006). Design of trees in the hose model: The balanced case. OPERATIONS RESEARCH LETTERS, 34(6), 601-606 [10.1016/j.orl.2005.09.005].
Italiano, Gf; Leonardi, S; Oriolo, G
Articolo su rivista
File in 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/2108/38562
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 15
social impact