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.
Tipologia: | Articolo su rivista | |
Citazione: | Brightwell, G., Oriolo, G., & Shepherd, F.B. (2001). Reserving resilient capacity in a network. SIAM JOURNAL ON DISCRETE MATHEMATICS, 14(4), 524-539. | |
Lingua: | English | |
Settore Scientifico Disciplinare: | Settore MAT/09 - Ricerca Operativa | |
Revisione (peer review): | Sì, ma tipo non specificato | |
Tipo: | Articolo | |
Rilevanza: | Rilevanza internazionale | |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1137/S0895480100368189 | |
Stato di pubblicazione: | Pubblicato | |
Data di pubblicazione: | 2001 | |
Titolo: | Reserving resilient capacity in a network | |
Autori: | ||
Autori: | Brightwell, G; Oriolo, G; Shepherd, F B | |
Appare nelle tipologie: | 01 - Articolo su rivista |