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.|
|Settore Scientifico Disciplinare:||Settore MAT/09 - Ricerca Operativa|
|Revisione (peer review):||Sì, ma tipo non specificato|
|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:||Brightwell, G; Oriolo, G; Shepherd, F B|
|Appare nelle tipologie:||01 - Articolo su rivista|