Reserving resilient capacity for a single commodity with upper-bound constraints

Continuing research begun in a previous study [SIAM J Discr Math 14 (2001), 524-539], 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. In the case where each arc has its own upper bound, we explain why no such results can hold, but we do give an efficient algorithm for the case where we are asked for a reservation on a fixed set of arc-disjoint paths. We consider the case where we are free to reserve on each arc as much capacity as we want but only in bundles of fixed size. (C) 2003 Wiley Periodicals, Inc