Centre for Discrete and Applicable Mathematics
	CDAM Research Report, LSE-CDAM-98-04 March 1998

Abstract

We examine various problems concerning the reservation of non-shared capacity for traffic in a network between source-destination pairs so as to be ``resilient'' against one or more network failures. In the simplest version of the problem we consider, the resilience requirement is that for a pair  (s,t),  on the failure of any one arc of the network, there is sufficient reserved capacity in the remainder of the network to support an  (s,t)  flow of some given value  T.  The most striking results come in 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 minimum cost network flows. Unlike traditional network flow problems, however, the integral version does not come for free: we do however give a polynomial time 1/14-approximation algorithm, and show that this is best possible. These algorithms can also be adapted to solve other versions, for instance in an acyclic network when the reserved capacity has to constitute an integer flow. We leave many problems open, and provide a number of examples.

A compressed (gzip) PostScript file (128 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-98-04, 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)-171-955 7732. Fax: +44(0)-171-955 6877. Email: info@maths.lse.ac.uk

		Introduction to the CDAM Research Report Series.
		CDAM Homepage.

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