Centre for Discrete and Applicable Mathematics

 CDAM Research Report, LSE-CDAM-2000-03

March 2000

Reserving Resilient Capacity with Upper Bound Constraints

G. Brightwell, G. Oriolo, and F.B. Shepherd


Continuing research begun in an earlier paper, we investigate problems of reserving capacity in the arcs of a network, subject to the constraint that, on the failure of any one arc, there is enough reserved capacity on the remaining arcs to support a flow of value  T  from a source  s  to a destination  t.  We also impose upper bounds on the amount of capacity we may reserve on the arcs: this alters the nature of the problem.
In the case where each arc has the same upper bound, we investigate the strategy of finding the minimum-cost reservation that is itself an acyclic  (s,t)  flow: we show that such a reservation is easy to find, always has a simple form, and has a cost at most twice that of the optimal solution.
We investigate other related problems.

A compressed (gzip) PostScript file (127 kB) with the full contents of this report can be downloaded by clicking here.

Alternatively, if you like a free hard copy of this report, please send the number of this report, LSE-CDAM-2000-03, together with your name and postal address to:
CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
Houghton Street
London WC2A 2AE, U.K.
Phone: +44(0)-20-7955 7732.
Fax: +44(0)-20-7955 6877.
Email: info@maths.lse.ac.uk

Introduction to the CDAM Research Report Series.
CDAM Homepage.

Copyright © London School of Economics & Political Science 2000

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html.