Continuing research begun in a previous study [SIAM J Discr Math 14 (2001), 524-539], we investigate problems of reserving capacity in the arcs of a network, subject to the constraint that, on the failure of any one arc, there is enough reserved capacity on the remaining arcs to support a flow of value T from a source s to a destination t. We also impose upper bounds on the amount of capacity we may reserve on the arcs: This alters the nature of the problem. In the case where each arc has the same upper bound, we investigate the strategy of finding the minimum-cost reservation that is itself an acyclic (s, t) flow: We show that such a reservation is easy to find, always has a simple form, and has a cost at most twice that of the optimal solution. In the case where each arc has its own upper bound, we explain why no such results can hold, but we do give an efficient algorithm for the case where we are asked for a reservation on a fixed set of arc-disjoint paths. We consider the case where we are free to reserve on each arc as much capacity as we want but only in bundles of fixed size. (C) 2003 Wiley Periodicals, Inc.

Brightwell, G., Oriolo, G., Shepherd, F.b. (2003). Reserving resilient capacity for a single commodity with upper-bound constraints, 41(2), 87-96 [10.1002/net.10064].

Reserving resilient capacity for a single commodity with upper-bound constraints

ORIOLO, GIANPAOLO;
2003-01-01

Abstract

Continuing research begun in a previous study [SIAM J Discr Math 14 (2001), 524-539], we investigate problems of reserving capacity in the arcs of a network, subject to the constraint that, on the failure of any one arc, there is enough reserved capacity on the remaining arcs to support a flow of value T from a source s to a destination t. We also impose upper bounds on the amount of capacity we may reserve on the arcs: This alters the nature of the problem. In the case where each arc has the same upper bound, we investigate the strategy of finding the minimum-cost reservation that is itself an acyclic (s, t) flow: We show that such a reservation is easy to find, always has a simple form, and has a cost at most twice that of the optimal solution. In the case where each arc has its own upper bound, we explain why no such results can hold, but we do give an efficient algorithm for the case where we are asked for a reservation on a fixed set of arc-disjoint paths. We consider the case where we are free to reserve on each arc as much capacity as we want but only in bundles of fixed size. (C) 2003 Wiley Periodicals, Inc.
2003
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore MAT/09 - RICERCA OPERATIVA
English
Capacity reservation; Network flows; Resilience
Brightwell, G., Oriolo, G., Shepherd, F.b. (2003). Reserving resilient capacity for a single commodity with upper-bound constraints, 41(2), 87-96 [10.1002/net.10064].
Brightwell, G; Oriolo, G; Shepherd, Fb
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/49707
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 9
social impact