CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishWe 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 |
File in questo prodotto:
Copyright © 2020