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

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

0.00 Avg rating0 Votes
Article ID: iaor20032478
Country: United States
Volume: 41
Issue: 2
Start Page Number: 87
End Page Number: 96
Publication Date: Feb 2003
Journal: Networks
Authors: , ,
Abstract:

Continuing research begun in a previous study, 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.

Reviews

Required fields are marked *. Your email address will not be published.