{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T11:28:56Z","timestamp":1791026936479,"version":"4.1.0"},"reference-count":27,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2001,1]]},"abstract":"<jats:p>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. For 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) flow 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.<\/jats:p>\n                  <jats:p>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 find a minimum cost fractional solution, based on finding successive shortest paths in the network. Unlike traditional network flow problems, the integral version is NP-hard: we do, however, give a polynomial time $\\frac{15}{14}$-approximation algorithm in the case k=1 and show that this bound is best possible unless P = NP.<\/jats:p>","DOI":"10.1137\/s0895480100368189","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"524-539","source":"Crossref","is-referenced-by-count":25,"title":["Reserving Resilient Capacity in a Network"],"prefix":"10.1137","volume":"14","author":[{"given":"G.","family":"Brightwell","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"G.","family":"Oriolo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"F. B.","family":"Shepherd","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,1]]},"reference":[{"key":"R1","unstructured":"A. K. Ahuja, T. L. Magnanti, and J. B. Orlin,\n                      Network Flows\u2014Theory, Algorithms, and Applications\n                      , Prentice Hall, Englewood Cliffs, NJ, 1993."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018984102311"},{"key":"R3","unstructured":"D. Alevras, M. Gr\u00f6tschel, and R. Wess\u00e4ly,\n                      Capacity and Survivability Models for Telecommunication Networks\n                      , Technical Report 97\u201024, Konrad\u2010Zuse\u2010Zentrum f\u00fcr Informationstechnik Berlin, Berlin, Germany, 1997."},{"key":"R4","first-page":"1","volume":"57","author":"Ascheuer N.","year":"1998","journal-title":"Optima"},{"key":"R5","unstructured":"A. Balakrishnan, T. Magnanti, J. Sokol, and Y. Wang,\n                      Modeling and Solving the Single Facility Line Restoration Problem\n                      , Working Paper OR 327\u201098, Operations Research Center, MIT, Cambridge, MA, 1998."},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623494279134"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1287\/opre.28.5.1074"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/S0025-5610(97)00079-8"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.8.3.243"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/PL00011390"},{"key":"R11","unstructured":"G. Brightwell, G. Oriolo, and F. B. Shepherd,\n                      Some Strategies for Reserving Resilient Capacity\n                      , LSE CDAM Report 98\u201004, London School of Economics, London, UK, 1998."},{"key":"R12","unstructured":"G. Brightwell, G. Oriolo, and F. B. Shepherd,\n                      Reserving Resilient Capacity with Upper Bound Constraints\n                      , LSE CDAM Report 2000\u201003, London School of Economics, London, UK, 2000."},{"key":"R13","unstructured":"G. Brightwell and F. B. Shepherd,\n                      Consultancy Report: Resilience Strategy for a Single Source\u2010Destination Pair\n                      , LSE CDAM Report 96\u201022, London School of Economics, London, UK, 1996."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"S. J. Bye and M. Herzberg,\n                      An optimal spare\u2010capacity assignment model for survivable networks with hop limits\n                      , in Proceedings of GLOBECOM, San Francisco, 1994, pp. 1601\u20131606.","DOI":"10.1109\/GLOCOM.1994.513045"},{"key":"R15","unstructured":"S. J. Bye and M. Herzberg, Spare\u2010capacity assignment in survivable networks for multi\u2010link and node failures with hop limits, in Proceedings of Networks\u201994, 1994, pp. 381\u2013386."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90009-2"},{"key":"R17","unstructured":"Andr\u00e1sFrank, Connectivity and network flows, Elsevier, Amsterdam, 1995, 111\u201317797i:05084"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"M.Gr\u00f6tschel, C.Monma, M.Stoer, Design of survivable networks, Handbooks Oper. Res. Management Sci., Vol. 7, North\u2010Holland, Amsterdam, 1995, 617\u20136721420875","DOI":"10.1016\/S0927-0507(05)80127-6"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050077"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"R. R. Irashko, M. H. MacGregor, and W. D. Grover,\n                      Optimal capacity placement for path restoration in mesh survivable networks\n                      , IEEE International Conference on Communications, Dallas, 1996, pp. 1568\u20131574.","DOI":"10.1109\/ICC.1996.535181"},{"key":"R21","unstructured":"T. Magnanti, P. Mirchandani, and R. Vachani,\n                      Modelling and Solving the Capacitated Network Loading Problem\n                      , MIT OR Working Paper, OR 239\u201091, MIT, Cambridge, MA, 1991."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580612"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1287\/opre.43.1.142"},{"key":"R24","unstructured":"T. Magnanti and Y. Wang,\n                      Polyhedral Properties of the Network Restoration Problem\u2014With the Convex Hull of a Special Case\n                      , Working Paper OR 323\u201097, Operations Research Center, MIT, Cambridge, MA, 1997."},{"key":"R25","doi-asserted-by":"crossref","unstructured":"H. Sakauchi, Y. Nishimura, and S. Hasegawa,\n                      A self\u2010healing network with an economical spare\u2010channel assignment\n                      , in Proceedings of GLOBECOM, San Diego, CA, 1990, pp. 438\u2013443.","DOI":"10.1109\/GLOCOM.1990.116551"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1111\/j.1475-3995.1996.tb00045.x"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"B. D. Venables, W. D. Grover, and M. H. MacGregor,\n                      Two strategies for spare capacity placement in mesh restorable networks\n                      , IEEE International Conference on Communications, Geneva, 1993, pp. 267\u2013271.","DOI":"10.1109\/ICC.1993.397269"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0895480100368189","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:25:47Z","timestamp":1787322347000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0895480100368189"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,1]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2001,1]]}},"alternative-id":["10.1137\/S0895480100368189"],"URL":"https:\/\/doi.org\/10.1137\/s0895480100368189","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,1]]}}}