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.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.
