We examine various problems concerning the reservation of capacity in a given network, where each arc has a per-unit cost, so as to be resilient against one or more arc failures. or a given pair (s, t) of nodes and demand T, we require that, on the failure of any k arcs of the network, there is sufficient reserved capacity in the remainder of the network to support an ( s, t) ow of value T. This problem can be solved in polynomial time for any fixed k, but we show that it is NP-hard if we are required to reserve an integer capacity on each arc. We concentrate on the case where the reservation has to consist of a collection of arc-disjoint paths: here we give a very simple algorithm to nd a minimum cost fractional solution, based on finding successive shortest paths in the network. Unlike traditional network ow problems, the integral version is NP-hard: we do, however, give a polynomial time 15/14-approximation algorithm in the case k = 1 and show that this bound is best possible unless P = NP.

Brightwell, G., Oriolo, G., Shepherd, F.b. (2001). Reserving resilient capacity in a network. SIAM JOURNAL ON DISCRETE MATHEMATICS, 14(4), 524-539 [10.1137/S0895480100368189].

Reserving resilient capacity in a network

ORIOLO, GIANPAOLO;
2001-01-01

Abstract

We examine various problems concerning the reservation of capacity in a given network, where each arc has a per-unit cost, so as to be resilient against one or more arc failures. or a given pair (s, t) of nodes and demand T, we require that, on the failure of any k arcs of the network, there is sufficient reserved capacity in the remainder of the network to support an ( s, t) ow of value T. This problem can be solved in polynomial time for any fixed k, but we show that it is NP-hard if we are required to reserve an integer capacity on each arc. We concentrate on the case where the reservation has to consist of a collection of arc-disjoint paths: here we give a very simple algorithm to nd a minimum cost fractional solution, based on finding successive shortest paths in the network. Unlike traditional network ow problems, the integral version is NP-hard: we do, however, give a polynomial time 15/14-approximation algorithm in the case k = 1 and show that this bound is best possible unless P = NP.
2001
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. (2001). Reserving resilient capacity in a network. SIAM JOURNAL ON DISCRETE MATHEMATICS, 14(4), 524-539 [10.1137/S0895480100368189].
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/49710
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 28
  • ???jsp.display-item.citation.isi??? 25
social impact