Reserving Resilient Capacity in a Network.
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.  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
Introduction
1.1

Overview

A commonly encountered network design problem is that of reserving capacities in a network so as to
support some given set of pairwise traffic demands. Algorithms for this network capacity allocation
problem have been developed by a number of groups, see for example [6, 8, 9, 21, 22, 23]. These are
primarily based on polyhedral methods. One significant drawback to the capacity reservation problem
discussed, and especially to the successive shortest path approach, is that if we simply reserve capacity
along a single path, we make ourselves totally vulnerable to the failure of any arc (or node) along our
chosen path. In many practical settings, this is not acceptable, and we wish to reserve our capacities
so as to allow for the failure of any one arc of the network.
Several groups have recently addressed this issue of "resilience" or "survivability" in network design
problems, e.g., [2, 3, 5, 10, 14, 15, 20, 24, 25, 26], to name a few. As with the preceding batch
of references, these are also primarily based on polyhedral or branch and cut methods (although
computationally, these problems prove to be dramatically more difficult to solve in practice (cf [10]))
and and hence if they terminate, they usally produce an optimality certificate. This aspect of this
approach is very desirable in situations where (i) costs and data are 'certain' and (ii) there is time
available to solve the optimization problem off-line. These conditions are often not met, however,
and consequently many of the network planning tools in the telecommunication industry solve the
'vanilla' form of the capacity allocation problem by successively solving a shortest path problem for
each demand pair incrementing loads on the arcs of the shortest path by the demand
for that pair. 1 In its favour, this approach is fast and allows for trivial implementation in software.
Unfortunately, one easily concocts examples where this approach produces solutions arbitrarily far
from the optimum. On the other hand, one may also produce examples where the exact methods do
not terminate or exhibit poor running times; in addition, they may require substantial mathematical
sophistication on the part of its implementors. Another situation where single source-destination pair
algorithms are sought is in on-line settings. This area is becoming increasingly important as network
management becomes a key concern of network operators. This is largely driven by the changing
nature of demands from their customers. In particular, bursty or short-term requests for connectivity
are becoming increasingly common.
The present paper is dedicated adapting the successive shortest path heuristic to be able to find
resilient capacity reservations. Thus we restrict ourselves throughout to the special case of the problem
with a single source-destination pair of nodes; we show that even this case presents some surprising
difficulties. This case may be equally viewed as an extension of finding a minimum cost flow for a
single source-destination pair. (Overviews of previous computational and theoretical work on such
survivability and augmentation problems can be found in [18] and [17].)
We adopt the viewpoint that the network, with specified nodes s and t, is given to us, along with a
per-unit cost c a for each arc a, and that we are free to reserve, once and for all, as much capacity as
we like on whatever arcs we choose. Our objective is to find a "reservation vector" x minimizing the
total cost
a c a x a , subject to supporting a given target amount T of traffic from s to t, even if any
one (or, more generally, any k) of the arcs in the network fails.
This rough description of the problem admits many different versions, depending on the type of
network we are dealing with, the way we are required to recover from arc failures, and especially on
any structure imposed on the vector of reserved capacities itself. In this paper, we consider two types
of constraints on the capacity reservation vector.
1 Costs are often altered so that they exponentially increase as the load on an edge approaches its capacity.
1. Integrality: We may be forced to reserve capacity in discrete amounts, so that our reservation vector
must be integral.
2. Structural: It may be required that our reservation vector be formed by selecting a collection of
arc-disjoint (s; t)-paths (i.e., directed paths from s to t in the network), and assigning a capacity to
each path - we call such a reservation a diverse-path reservation.
We begin Section 2 by studying resilient diverse-path reservations. This version arose out of a problem
encountered by British Telecom which was solved by two of the authors in a consultancy report [13]
- this work forms the basis of Section 2.1. The research described in this paper is partly an attempt
to determine conditions under which such diverse-path solutions will be optimal in general.
Diverse-path solutions have several features which are attractive to network planners. For a start, a
diverse-path routing may be "hardwired" at the terminating nodes, thus decreasing routing complexity.
If a traffic flow control is centralized, then this allows load balancing of traffic over the collection of
diverse paths. Even if this is not the case, as in a noncooperative network, the restoration phase is
much simpler since an arc failure may be treated as a path failure, and traffic routed along the path
may be shifted to the remaining non-failed paths. Finally, like shortest paths, they are conceptually
simple to visualize. In Section 1.3 we give an overview of different types of resilience and restoration
and discuss some of the issues involved.
In Sections 2.1 and 2.2 we describe an extremely simple algorithm to find a minimum cost resilient
diverse-path reservation. If the paths are pre-specified, this may be used to find the optimal integral
reservation. If the paths are not specified, the integer version of this problem turns out to be NP-hard.
Here instead we give a polytime 1
14 -approximate algorithm in the case of resilience against the failure
of one arc, and show this bound is the best possible (if P 6= NP). Similar results hold if k takes other
values, or is unrestricted.
In Section 3, we discuss the general problem of resilience with no side-constraints. We give several
examples of basic optimal solutions, showing that we do not always obtain anything resembling a
diverse-path reservation in the general case.
We show that the integral resilience problem is NP-hard. However, we do show that the naive algorithm
that allocates capacity T to the arcs of a cheapest pair of arc-disjoint (s; t)-paths gives a solution with
at most k times the cost of an optimal solution.
1.2 Notation and Definitions
We start with basic definitions and facts concerning flows in networks.
Throughout, we suppose (sometimes implicitly) that we are given a directed graph (network)
with node set V and arc set A. We shall always assume that D comes with two nodes permanently
fixed as the source (or origin) s and the destination (or sink) t. We also suppose that we
are given a rational number T (usually an integer) representing the required traffic flow from s to t
through the network D in the case of failure. Finally, we are also given a vector (c a ) of non-negative
rational (again, usually integer) costs on the arcs a of D. Even though there may be parallel arcs, we
often use the notation (u; v) when no confusion arises.
For any S ' V , let
D (S) (or simply if the context is clear) denote the set of arcs with tail in
S and head in denote the set of arcs S). For a node v 2 V , we
we denote by [S; S 0 ] the set of arcs with tail in S and head in S 0 . We call
an (s; t)-set if s 2 S and t called s-minimal if the graph induced by
S contains a directed path from s to each node of S.
Let Q+ denote the set of non-negative rational numbers, so that Q A
is the set of all assignments of
a non-negative rational to each member of the arc-set A, which we will frequently view as a vector.
For any vector x 2 Q A
and A 0 ' A, we denote by
a2A 0 x a . We let I(x) denote the
support of x, that is
A vector x 2 Q A
is an (s; t) flow vector (or simply a flow) if x(ffi
and (therefore) x(ffi (t)). In this case, the value of the flow is
For any rational M and (s; t)-set S, the M-cut constraint for S is: i.e., the total
capacity of arcs leaving S is at least M . We define the M-cut polyhedron as
for each (s; t)-set S
Network flow theory asserts that for a given vector x 2 Q A , there is a flow vector w - x of value M if
and only if x 2 C(M;D). It is an exercise to show that in (1) we need only include the cut constraints
corresponding to s-minimal sets.
A vertex of a polyhedron P ' R n is an extreme point of P, i.e., a vector in P that is not a convex
combination of two other vectors in P. For a polyhedron P in R n , a vector y 2 P is a vertex if and
only if there is some linearly independent set of n inequalities defining P that are satisfied by y with
equality. Since we consider only polyhedra in R n
linear function is bounded below on P, then it
attains its minimum at a vertex; such a vertex is called a basic optimal solution to the minimization
problem.
1.3 Types of Resilience
We consider vectors
of reserved capacities on the arcs of D such that if any k arcs of D are
deleted, then the remaining arcs have sufficient capacity. A vector x 2 Q A
is (T; k)-resilient if, for each
set K of k arcs, the capacities on arcs in A \Gamma K are sufficient to admit an (s; t) flow of value T . As in
the previous section, this is equivalent to requiring that x satisfies the constraint x(ffi
for each (s; t)-set S and each subset K ae size k. In fact, it is easily shown that we need only
require these constraints for s-minimal sets S.
We also call a (T; 1)-resilient reservation T -resilient, and for the remainder of this section we do indeed
restrict ourselves to the case Everything here goes through in much the same way for the case
As with the standard network flow problem, the problem of finding a minimum cost T -resilient reservation
vector can be expressed as an optimization problem over a certain polyhedron, which we now
describe.
For any rational T , (s; t)-set S, and arc e (S), the partial T -cut constraint associated with the
is the constraint x(ffi T: The resilience polyhedron is defined by the system of
all partial cut constraints.
for each (s; t)-set S and e 2
Note that R(T; D) is empty if there is an (s; t)-set S with of size at most 1, and otherwise
R(T; D) is full-dimensional. Also note that if x 2 R(T; D), then setting any x results in a
vector in C(T; D). Thus if we reserve the capacities x, then even if an arc fails, there is still enough
capacity to build an (s; t) flow of value T . Conversely, any vector x not in R(T; D) fails the partial
T -cut constraint for some pair (S; e) and hence if e fails, there is not sufficient capacity in the network
to support a flow of value T . Therefore R(T; D) consists exactly of the T -resilient vectors, and the
problem of finding a minimum cost T -resilient reservation is that of minimizing the linear function
a2A c a x a over R(T; D).
A consequence of this formulation is that there is a polynomial-time algorithm to find a minimum
cost T -resilient vector. Indeed, it is easily seen that the separation problem for R(T; D) amounts to
solving jAj maximum flow problems. Still better, as noted previously by several researchers, we can
rephrase the problem as that of finding one (s; t) flow vector y a of size T for each failing arc (i.e., with
y a
along with a common upper bound x - y a whose cost is to be minimized: this formulation
constitutes a linear program with a polynomially bounded number of variables and constraints. This
is not offered as a practical approach however, and the remainder of the paper addresses the task of
finding more direct combinatorial algorithms.
Let us give an example, which also illustrates a possible limitation of our notion of resilience. Consider
the network D in Figure 1. For appropriate costs, the arc values in Figure 1(a) form a (unique)
minimum cost 6-resilient reservation vector: in other words, the vector shown is a vertex of the
polytope R(6; D). A "working flow" of value 6 for this network is displayed in Figure 1(b), where the
numbers in brackets denote the "spare capacity" for this flow. Note however that if the arc (u; t) were
to fail, and we are asked to redirect the one unit of traffic currently flowing along the path s !
then this cannot be done without altering flow values on paths which were unaffected by the arc's
failure. This might not be acceptable in some practical situations.
(a)213
s
(b)
s

Figure

1: A resilient reservation vector with
It is easily seen that this situation does not arise if we demand that our reservation vector x consist
of a collection of arc-disjoint paths, which is one motivation for considering that restriction.
Another way to refine the notion of resilience so as to address this issue is to replace the partial T -cut
constraints by stronger inequalities. The net partial T -cut constraint associated with a pair (S; e) is:
is net T -resilient if it satisfies all the net partial T -cut
constraints; we denote by N (T; D) the set of all such vectors. For instance, the reservation vector in

Figure

1(a) fails the net partial 6-cut constraint for (S; e) where It is
not hard to show that, given a net T -resilient reservation vector x, and any flow of value T , thought
of as a combination of traffic flowing down (s; t)-paths, on the failure of any arc, flow of value T can
be restored without altering the routing of any unaffected traffic. Net resilience is of course a much
stronger requirement than resilience, but it does share most of the good computational properties.
For more details, see the technical report [11], which is a longer version of the present paper.
We close this section with a brief discussion of other types of resilience. We have concentrated on the
case where we require resilience against one or more arc failures. One may also wish to guard against
node failures. We remark only that this problem can be formulated using our previous models by
applying standard splitting operations on nodes other than s and t.
Another possibility is that we may wish to guard against losing some fraction ff 2 [0; 1] of the flow on
each arc, giving, for each (S; e), the constraint:
A vector x satisfying these constraints will be called )-resilient. Note that if ff = 0, this leads
to a formulation for traditional network flows. If it is the partial T -cut constraint again. The
effect of intermediate values of ff can essentially be analyzed by duplicating arcs.
To be precise, suppose that ff = p=q is rational, and that we require an (ff; T )-resilient reservation x
in a network D. To model this, we form D 0 by taking q copies of each arc of D, each with the same
cost as in D. It is easy to check that a minimum cost reservation vector for D 0 that is qT -resilient
against the loss of any p arcs can be constructed from a minimum cost (ff; T )-resilient reservation in
D by duplicating the reservation on each set of multiple arcs.
One final possibility is that the structure of the reservation vector x when all arcs are functional is
of paramount importance. A likely scenario is that there is some value M such that the vector x is
required to admit an M -flow, that is, there is an (s; t) flow f of value M with f - x, or maybe even
that x itself is required to be an M -flow. We don't discuss such constraints in this paper, but we plan
to discuss this situation in a future paper [12], where we also consider the effect of imposing upper
bounds on the capacities that can be reserved on each arc.
Resilient Diverse-Path Reservations
As we have mentioned, our aim with resilience problems is often to reduce to the case where the
reservation has to form a collection of arc-disjoint paths, and we term such a reservation a diverse-
path reservation. We thus need to consider how we solve the problem once it has been reduced to this
special case.
We start with the case where the collection of diverse paths is fixed ahead of time. This forms the
basis for much of what follows and so we present it in detail. The material in the first two parts of
this section, written for a non-technical audience, appears as [13]. A more thorough handling of the
polyhedron considered herein (including a complete linear description of the integer hull) has been
given by Bienstock and Muratore - see [10]. The case can also be regarded as a special case of
a problem treated by Bartholdi, Orlin and Ratliff [7]; our methods give a somewhat simpler solution
in this special case.
2.1 Reservations on a Fixed Set of Paths
Suppose that we are given a network and two integers T and k, together with a source s and a
destination t, along with a fixed set of diverse paths from s to t on which capacity may
be reserved for (s; t) traffic. We want to ensure that, in the absence of any k of the paths P i , there
is sufficient capacity on the remaining paths to carry a given amount T of traffic from s to t. To
accomplish this requires us to fix a capacity x i for each path P i , and give each arc on path P i capacity
. The cost of reservations can be calculated from the per-unit total costs c i of the paths P i . Thus
in practice we can think of the network as consisting of just the two nodes s and t, with the P i being
single arcs of cost c i from s to t.
A diverse-path reservation as above is (T; k)-resilient if the total amount of reserved capacity, excluding
any k arcs, is at least T . We may assume that the paths P i are numbered in increasing order of per-unit
cost c i , so we can state the problem formally as follows.
k-Failure Allocation Problem.
Given a demand T , and a sequence of costs c
find non-negative real numbers x subject to the
conditions
For any k-set S '
We shall also consider the integral version of this problem.
A result that is fundamental in much of the rest of the paper is that the optimal allocation of capacities
(for any costs satisfying (4)) is always achieved by some vector z j;k of the form
ae
for some j between k m. Thus we need only find the appropriate j for which the cost is
minimized.
Of course, the single-failure problem is just the special case of the k-failure problem with
this case we denote by z j the vector z j;1 .
Theorem 1 An optimal solution to the k-Failure Allocation Problem is obtained at one of the solutions
z j;k .
Proof. Because of the symmetry of the situation, we know that there is an optimal solution such
that x 1 - x 2 - xm . Thus we lose nothing by including these inequalities as constraints. Once
we do this, we see that, if the constraint x all the other
resilience constraints given by the removal of k of the paths are automatically satisfied. Thus we may
reformulate the problem as follows.
Given a demand T , and a sequence of costs c 1 - c 2 - c m , find non-negative real numbers
to minimize
subject to the constraints x 1
We note for future reference that the same reformulation goes through if the x i are all constrained to
be integers.
Consider a basic optimal solution for the resulting linear program which necessarily satisfies m linearly
independent inequalities with equality. If there are j non-zero variables at the optimum, then the
only possibility is that all of the inequalities x 1
are satisfied with equality, i.e., that x
This is just the solution z j;k and the result follows.
Choosing amongst the various solutions z j;k is evidently not hard, and in fact the structure of the
problem allows a particularly simple procedure for doing this. The cost of solution z j;k is
which is best thought of as the average of c 1
. , and c j . We are trying to minimize A j;k , over the range of possible values
Note that the A j;k are decreasing in j up to the minimum, which is attained for the last j where
increasing thereafter: this unimodality property will be a recurring theme. Thus
for each . If this is the case, then we terminate and
z j;k is optimal. If we reach z m;k is the optimal solution.
allocation problems with integer capacity allocations
To find the optimal solution in the case where the allocated capacities x i are required to be integers
(and the demand T is an integer), we will show that the following procedure suffices.
First find the optimal solution z j;k to the original (non-integral) k-failure Allocation Problem. Then
(if the z j;k
i are not already integers) consider the two integer solutions "nearest" to z j;k , as follows.
(a) Set r equal to either bT=(j \Gamma k)c or dT=(j \Gamma k)e. (Here dae denotes the next integer above the real
number a, and bac the next integer below.) Note that r may be zero if T
(b) If r is one of the two chosen values and r is nonzero, we attempt to construct a solution x with
all the non-zero x i , except possibly one, equal to r. To do this, we set l
(The choice of l ensures that
could have l ? m, but this is not possible with
Note that this is a feasible solution, since removing any k of the x i leaves capacity at least (l
which is constructed to be at least T .
(c) We now have either one or two candidate integral solutions, corresponding to the two choices of
r in (a). We denote by z j;k;+ the solution with it is feasible), and by z j;k;\Gamma the
solution with (which is always feasible). To finish, just calculate the costs of the two
solutions, and choose the lower.
Theorem 2 Suppose we have an instance of the k-Failure Allocation Problem in which the optimal
solution is z j;k . Then the optimal solution x with all the x i integer is either
Proof. We work with the reformulation of the problem as in the beginning of the proof of Theorem 1,
which, as we noted, is also valid for the integer case. Suppose that x is an optimal integer solution.
Clearly, since the only constraints on the first k variables are that x 1 - x 2 - x k+1 , we will
have at the optimum. Now suppose that some x j is non-zero, but that not all
of x are equal. Then let i be the minimum index with x
the previous observation. Also let x l be the last non-zero variable, so
increasing x i by one, and decreasing x l by one. This keeps the solution feasible, since all the variables
remain in the right order, and x unaltered. Also, this operation does not increase the
cost.
We have thus shown that one may restrict attention to integral solutions with the following form: for
some j with k we have all of x 1 , . , all of x equal to 0. If
the value of x j is q, then the common value of the earlier x i is which will be an
integer, at least q.
At this point, there are still potentially a large number of candidate solutions; in fact, there is one for
each integer value of x 1 at least T=m, namely to set e, and
We next observe that the integer solution given above is a convex combination of the two "fractional"
solutions z j;k and z j \Gamma1;k . To be precise, our solution is
z
Thus each of our candidate integral solutions is a convex combination of two consecutive z i;k s. Let
A be the set of all such convex combinations; we think of A as a "path" with vertices corresponding
to z We note that any vector on this path gives a feasible solution. Next observe
that the first coordinate values are decreasing along A, and the values for any vector in A are thus
determined by the first coordinate x 1 . Moreover, this solution will be integral if and only if x 1 is an
integer. Also, since the costs of the vertices z i;k are unimodal, and cost is a linear function between
each pair of vertices, the solution cost is unimodal along A, with the minimum obtained at the vertex
corresponding to some z j;k , with first coordinate equal to, say, r. These arguments show that the
lowest cost integral solution among our candidates, and so the overall optimal integer solution, is the
solution on A corresponding to taking x 1 to be either dre or brc, i.e., taking either z j;k;+ or z j;k;\Gamma .
This completes the proof.
We close this section with a bound relating the costs of the optimal integral and fractional solutions.
Proposition 3 For any j ? k - 1, let O be the cost of a solution z j;k and O 0 be the cost of the
integral solution z j;k;\Gamma . Then O
T .
Proof. Recall that, in the solution z j;k , the j cheapest paths are chosen, each with capacity
k). The "rounded" solution z j;k;\Gamma is obtained from this by taking the l \Gamma 1 cheapest paths
with capacity k)e, and the next cheapest path with capacity
The first observation is that the average cost per unit of reservation in z j;k;\Gamma is no greater than that
in z j;k . Thus O 0 =O is at most the ratio of the total numbers of units of capacity reserved in the two
allocations.
In z j;k , a total of jT=(j \Gamma units of capacity are allocated, while in z j;k;\Gamma , the total is (l \Gamma 1)x
Hence we have
O 0
O
Now (j by definition of x, so we have the estimate as claimed.
Corollary 4 If O I is the cost of the optimal integral solution to an instance of the k-failure allocation
problem with target flow T , and OF the cost of the optimal fractional solution to the same problem,
then O I
Consideration of the proof of Proposition 3 shows that the ratio (1 in general be
improved. Indeed, if our network consists of a large number M of paths of cost 1, then it is easy to
see that O I
2.2 Diverse-Path Reservations without Specified Paths
We now consider what happens when we are still required to find a resilient reservation consisting of
a set of diverse paths in a given network D, but we are not restricted as to what paths we may use.
We give a fast algorithm for the fractional case, but show that the integral case is NP-hard.
We start with the fractional case. The results of Section 2.1 imply that the optimal solution will have
as support the arcs of some j ? k diverse paths, with each arc in the support given capacity T=(j \Gamma k).
Of course, j can only take integer values up to the (s; t)-connectivity -(D) of D. We may take
advantage of this structure and apply the successive shortest path method - c.f. [1] - for minimum
cost flow problems, thus only needing to solve -(D) shortest path problems.
For an arc a = (u; v) 2 A, we let a \Gamma denote an "artificial" arc (v; u), not present in D. In the course
of the following algorithm, we construct a series of auxiliary digraphs D j , each of which will contain
exactly one of each pair a; a \Gamma . We assume that we are given a digraph D with -(D) ? k.
f
While (D j contains a directed (s; t)-path)
Let Q j be a minimum c j -cost directed (s; t)-path in D j
z j+1;k be the vector obtained by assigning
to each arc in P j+1
then Output(z j;k ) and Quit
are the same as D
if a 2 R
remove a \Gamma , and include a with cost c j+1
if a 2 F
remove a, and include a \Gamma with cost c j+1
EndWhile
We will also refer to the version of the algorithm which does not terminate early and thus generates
a reservation vector z j;k for every
Proposition 5 (c.f. [1]) Let c be a nonnegative vector of arc costs in a network A). The
algorithm Paths finds a minimum cost (T; k)-resilient diverse-path reservation.
To establish correctness, we need two facts. First, for each j, the collection P j induces a minimum
cost collection of j diverse (s; t)-paths; this follows from the correctness of the successive shortest
path method. This implies that each solution z j;k is the minimum cost solution using j paths, and
hence the minimum cost (T; k)-resilient vector is among these vectors z j;k . Moreover, traditional flow
theory implies that for each is a minimum cost flow of value subject to the
capacities on each arc. Second, as we now show, the sequence cost(z j;k ) is unimodal for
termination is justified.
Proposition 6 Let h, i and j be such that k ! h
Proof. Suppose the contrary: there exists h, i, j, with
and cost(z i;k
i\Gammak and choose - 2 (0; 1) such that i
is a flow of value does not exceed T=(i \Gamma 1) on any
arc. Thus by the remarks preceding the proposition, cost(z 0
maxfcost(z h;k ); cost(z j;k )g, a contradiction. 2
integer diverse-path reservations
We now consider the problem of finding a minimum cost T -resilient integral reservation whose support
is a collection of diverse paths. Thus we denote by idp the problem each instance of which consists
of a network with two specified nodes s; t together with nonnegative integer costs on the arcs and an
integer T . An optimal solution for an instance will be a minimum cost T -resilient reservation obtained
by reserving integer capacities on a collection of diverse (s; t)-paths.
The results of the previous section once again show that the support of an optimal such solution will
consist of a collection of diverse (s; t)-paths the arcs of the first
reserve a commonamount, r, of capacity, and the last path's arcs will reserve capacity
r. 2 We now show that the subproblem of idp with denoted by 3-idp, is NP-hard.
Let 2div-paths denote the problem of determining whether a given digraph D, with four distinct
nodes contains a pair of arc-disjoint paths
Fortune, Hopcroft and Wyllie [16] show that this problem is NP-complete.
Suppose that we are given an instance of 2div-paths as above. Construct a digraph obtained from
D by adding new nodes s; t as well as the arcs (s;
2, 1 and 2 respectively. All remaining arcs will have cost zero. This is our instance of 3-idp. From
the preceding section, we deduce that an optimal 3-resilient reservation on diverse paths will either
have support on (i) 2 diverse paths, in which case capacity 3 is reserved on each of the arcs of these
paths, or (ii) 3 diverse paths in which case two of the paths will have reserved capacity 2 and the third
capacity 1.
Note that the cheapest collection of 2 diverse paths has cost 5 and hence any solution of the form (i)
will have cost at least 15. Next note that if there exists a positive solution to the instance of 2div-
paths, with P i a path between s then by assigning capacity 2 to the arc (s; t) and the
arcs of P 1 , and capacity 1 to the arcs of P 2 we obtain a solution to 3-idp of cost 14. Conversely, if
the instance of 2div-paths has no solution, then any "3-path" solution to 3-idp will use only paths
of cost 3, from which we deduce that the reservation will cost at least 15. Thus the optimal solution
to the instance of 3-idp is 14 if and only if the instance of the 2-disjoint path problem has a positive
solution.
Note that the above result shows that approximating 3-idp to within a factor of (1 + 1) is NP-
hard. On the other hand, Proposition 3 implies that applying the rounding procedure to an optimal
fractional solution will yield a (1+ 1)-approximation to the optimal integral solution. We now improve
this latter bound.
We continue to restrict attention to the case allow T to take arbitrary integer values.
Consider the polynomial time algorithm A (based on Paths) that finds, for each value of j, the
fractional solution z j;1 based on some cheapest set of j diverse paths, and the two "rounded" integer
solutions z j;1;\Gamma and z j;1;+ , and chooses the best among all of the integer solutions. The algorithm A
In essence we thus need to solve an integer 2-multicommodity flow problem where both commodities have the same
origin and destination.
can fail to find the optimal integer solution because it may use a minimum cost set of l paths in which
the costs are distributed "more evenly" between the paths (in particular, the most expensive path is
cheaper) than in some other (not necessarily even minimum cost) set of l paths. All we know is that
an optimal solution for an instance of idp will have the same form as either z l;1;\Gamma or z l;1;+ for some
l, since it will arise from a similar rounding process applied to some collection of diverse paths.
Let OF be the cost of a fractional optimum solution, O I the cost of an integer optimum solution, and
OA the best solution among those considered by the algorithm, i.e., the value returned by A. Clearly
we have OF - O I - OA . We prove the following result.
Theorem 7 The algorithm A is a 1
14 -approximate algorithm for idp with that is, for each
instance: OA - 15O I . Moreover, there is no ffl-approximate algorithm for idp with
latter statement, of course follows from the previous example showing that the decision version of
idp with We note that the quality of approximation by the algorithm depends
greatly on the input T . If we view A as an infinite collection of algorithms fA T g 1
T=1 , each restricted
to instances with a fixed value of T , then many of these are ffl-approximate algorithms with
14 .
Indeed, Proposition 3 tells us that, for each T , OA I .
Furthermore, we note in the course of the proof that, for exactly solves the
subproblem T -idp.
Proof. Suppose an optimum integer solution z   uses paths each with reserved capacity
r, and path P l+1 , with reserved capacity y. We may assume that 0 - y - r, l - 2, and that r
is either bT=(l \Gamma 1)c or dT =le, with y, since otherwise there is a solution of one of
the given forms with no greater cost using the same set of paths, by Theorem 2. We also have that
Clearly we can assume that O I 6= OA . In particular, this means that otherwise one of
z l+1;1 or z l;1 would be an integral solution found by A whose cost was at most that of z   . Thus
The values of T and r determine y and l and, as we noted before the proof, we may assume that
7. There are thus only a finite number of possible forms of z   (in
just 23 pairs (T; r) satisfy all the restrictions mentioned so far), and we shall rule all these out
using the same basic method. At this point, let us observe that there are no cases with
or 12; for these values of T , any r not dividing T exactly is not of the form bT=(l \Gamma 1)c or dT =le for
any integer l. In particular, we may assume that we have T - 3.
We require a lower bound on the cost of z   . Notice that z   can be written as y times the characteristic
vector of some set of l times the characteristic vector of some set of l
diverse paths. Let C i be the cost of reserving one unit of capacity on the arcs in a cheapest collection
of i diverse paths. So we have O I = C(z
Our algorithm A considers some integer solution of the same form as z   (i.e., the same values of
using some set of l +1 paths of cost C l+1 . The cost of this solution is at most what it would
be if all the l +1 paths had the same cost, which is (lr +y)C l+1 =(l +1). So OA is at most this quantity,
i.e.,
We aim for a similar bound on C l , and to get this we need to look at a solution produced by A on at
most l paths. Accordingly, let r there is some integer solution with reserved capacity
r 0 on the first m ! l paths from C l , and v - r 0 on one further path, with total of reserved capacities
on all the paths equal to T Our algorithm will have looked at an integer solution with a cost at
least as good as some solution of this form, and the average cost of a path in any solution of this form
is at most C l =l, as in the proof of Proposition 3.
So we have OA -
We conclude that
O I -
After a little manipulation, this becomes
O I
G:
We could now run through all the 23 cases separately and show that G - 1=15 in each case. Let us
proceed slightly more systematically.
First, we consider all cases with l = 2. In this case, we have r which implies
that r
Next, if This gives
l - 2. Assume from now on that l; r - 3. This implies that T - 7 and that r ! T=2.
If r we have G 1), and we are
done if 4. On the other hand, if
thus the only two cases with
are
From here on in, there seems to be no great saving on dealing with all the cases individually. Here
are all the cases not so far ruled out.
All the values for G above are less than 1=15, so the theorem is proved.
It is clear that this technique can be used to prove similar results for other values of k. If k is
unrestricted, it turns out that the algorithm Paths is a 1
5 -approximation algorithm for idp, and that
this is best possible, i.e., there is no ffl-approximation algorithm for idp with
omit the details.
Resilient Reservations with no Restrictions
3.1 Examples of Vertices of R(T;D)
Although the problem of finding minimum cost resilient reservations can be solved in polynomial
time, we have been unable to find a truly practical algorithm for the problem. It is natural to believe
that there might be an algorithm which uses some generalization of the pivot operation (i.e., cycle
augmentations) for standard minimum cost flows. In order to explain why it is likely to be difficult
to find any such algorithm, we consider various examples of vertices of polyhedra R(T; D) - these are
basic optimal solutions to the resilience problem, and we also term these basic resilient reservations -
which are far from the pleasant diverse-path reservations we have been working with so far. We have
already seen one such example in Figure 1: two more are given in Figures 2 and 3 below. Here and
throughout this section, we restrict attention to the single-failure case.

Figure

2: A basic resilient reservation with a cycle

Figure

3: A vertex of both R(T; D) and N (T; D)
By definition, x is a vertex of R(T; D) if (i) x 2 R(T; D) and (ii) there is some subset of jAj linearly
independent constraints, from the system of non-negativity and partial T -cut constraints, which are
satisfied with equality by x. If the partial T -cut inequality for (S; e), where S is an (s; t)-set and e an
arc in is called a critical arc, and S is called a tight set,
for the reservation vector x.
One hope of understanding the structure of the vertices of R(T; D) is to understand the role of the
critical arcs. One may apply uncrossing techniques to show that if a is a critical arc, then there is no
tight set S for which a 2 For suppose this were the case, let e be a critical arc for S and let S 0
be a second (s; t)-set for which x(ffi
the left hand side is also equal to x(ffi In particular,
a Consider the case where e we have that
contradiction. The other cases follow similarly. This
immediately implies the following.
Proposition 8 If x 2 R(T; D) and all arcs in I(x) are critical, then I(x) is acyclic.

Figure

above shows a vertex of R(T; D) for the given digraph D in which the reservation vector
contains a cycle. The two arcs forming the cycle are not critical. Figure 4 shows another vertex x of
a polyhedron R(T; D) for which there are non-critical arcs a (the two arcs not incident with s and
with x a ? 0. (This example is also a basic optimal solution for the node-deletion version of the
problem; this reservation is resilient against the failure of any internal node.)
s

Figure

4: A basic resilient reservation for both standard and node-deletion versions
Further understanding of the structure of the vertices has eluded us; we offer two conjectures.
Conjecture 3.1 Let x be a vertex of R(T; D).
ffl There exists a directed path from s to t consisting only of critical arcs.
ffl There exists an (s; t)-set S such that the reserved capacities on all arcs in I(x) " have the
same value, and each arc in this set is critical.
Finally, we observe that basic resilient reservations may have components of the form pT
q for any
rational Indeed for any such p; q, Figure 5 displays such a vertex.
3.2 NP-completeness of Integer Resilience Problems, and an Approximation
Algorithm
We next show that the problem of finding a minimum cost integral T -resilient vector is NP-hard, even
in the single-failure case. We couch the problem as a decision problem.
Integer Resilience
Instance: a digraph D, with integer costs c ij on the arcs, with a single source s and destination t, a
target resilience T (integer), and a target cost C (integer).
q-p arcs
s
(pT)/q

Figure

5: A vertex of R(T; D) and N (T; D) with a component a given rational multiple of T
Question: is there an integer reservation vector x on the arcs of D such that c \Delta x - C, and such that
x is T -resilient?
Theorem 9 Integer Resilience is strongly NP-complete.
Proof. Certainly the problem is in NP, since checking T -resilience simply involves finding flows of
value T in the networks obtained by removing individual edges.
To prove the problem is NP-complete, we give a reduction from 3d-matching. Recall that an instance
of 3d-matching consists of three sets A, B, C of size n, and a collection T of m "triangles" each
containing exactly one element from each of A, B and C; the question is whether A can be
written as the disjoint union of n triangles from T .
Suppose that we are given an instance of 3d-matching as above. We show how to construct an
instance of Integer Resilience with m+ 3n arcs each of cost 1, n, or 2n, such
that there is a (4m 1)-resilient integer reservation of cost at most (2n
only if the original instance did possess a 3D-matching.
We take one node of D for each triangle abc 2 T , one node for each element of A
nodes s and t. We take four parallel arcs, each of cost 1, from s to each node corresponding to an
element of T . Each node abc has seven arcs leaving it: four, of cost 2n, go directly to t and one, of
cost n, to each of the constituent elements a, b and c. Finally, there is a single arc of cost n from each
element of A t.
Consider any T -resilient integer reservation vector x of cost at most (2n
First note that the reservation x must dominate a flow of value
otherwise there is a cut of capacity at most T . Look first at the set A 0 of "expensive" arcs not
incident with s. A flow of value necessarily costs 2n(T + 1) on A 0 . Thus the cost of x on A 0 is
at least 2n(T + 1), and equality is only possible if every arc in A 0 has reserved capacity just 1. Thus
on A 0 , the reservation looks like the characteristic vector of a set of T diverse paths.
Such a set of paths must include every arc arriving at t, and uses between 4 and 7 arcs from each node
of T . For be the number of reserved arcs leaving v. The cost of any integer T -resilient
reservation not of this form must be at least 2n(T arcs.
Now consider the reservation vector x on the set A 1 of arcs leaving s. Certainly the total cost of
the reservation on A 1 is greater than T must have reserved capacity at least 2.
Thus we see that, since the total cost of x is at most (2n the reservation on
A 0 does indeed form a set of T diverse paths, with d(v) 2 f4; 5; 6; 7g starting from each v 2 T .
For the reservations on the four arcs between s and v must total at least d(v), and the sum
of any three of them must be at least after deleting an arc there still exists a T -flow).
The minimum cost of such a reservation between s and v is just 4 if since then only 1 need
be reserved on each arc. For d(v) ? 4, one routinely checks that such a reservation costs at least
since arcs of capacity at least 2 are needed. So the total cost of x on A 1 consistent with the
values d(v) is at least
plus the number N of elements v for which We know that
v. Therefore N - n, with equality if and
only if just n elements of T , and for the remainder. In this case, the cost of x
on A 1 is otherwise is at least T
Hence, if there is such a reservation vector x of total cost just (2n are just
while the remainder have 4. A collection of T
paths on A 0 subject to these conditions must involve n elements of T for which the 3n arcs from these
elements to A [ B [C go to distinct nodes, i.e., a 3D-matching in the original instance.
Conversely, given a 3D-matching U , we can find a T -resilient reservation by reversing the argument.
We reserve capacity 1 on all arcs entering t, and all arcs leaving elements of U ; we further reserve
capacity 1 on arcs from s to elements of T n U , and capacity 2 on arcs from s to elements of U . It is
easy to check that this reservation is T -resilient, and has the required cost.
Of course, the requirement that all reservations be integers is crucial. However, notice that the
reservation we emerge with is actually net T -resilient as well, so the corresponding problem for net
resilience is also NP-hard.
On the positive side, there is a simple k-approximate algorithm for (T; k)-resilience in a network D - in
the fractional or integral case - namely to find and output the minimum cost diverse paths reservation
using which of course reserves capacity T on each arc of a cheapest set of k paths.
The following result states that this is indeed a k-approximate algorithm.
Proposition 10 If x is a (T; k)-resilient vector, then cx - 1
Proof. Let x be a minimum cost (T; k)-resilient vector. Define x 0 by setting, for each arc a,
Let S be any (s; t)-set. We claim that x
Suppose first that there is a set K of
k+1 , and so
If instead x a ! T
k+1 for all arcs a those in a set K of k arcs. Then x(ffi
and so x This proves our claim.
Now, since x for each (s; t)-set S, there exists an (s; t) flow x 00 of value (k+1)T such
that x 00 - x 0 , so in particular no arc has reserved capacity more than T ; thus x 00 is a (T; k)-resilient
vector.
As we remarked earlier, the diverse path reservation z k+1;k is a minimum cost (s; t) flow of value
subject to an upper bound T on the flow through any given arc. It follows that cz k+1;k -
Thus we have that the minimum cost diverse-path reservation has at most k times the cost of
an optimal (T; k)-resilient reservation. Of course, this is of greatest interest in the case 1. The
best possible: consider the following example. The network D has three nodes s,
u and t. There are k cost 1 from s to u, and r arcs of large cost c from u to t. The
minimum cost (1; k)-resilient reservation involves giving capacity 1 to the arcs between s and u, and
capacity 1
r\Gammak to the arcs between u and t, at a cost of k However, the minimum cost
diverse-path reservation, z k+1;k , uses only k+1 of the arcs from u to t, at a total cost of (k +1)(1+c).
For large c and r, the ratio between these two costs can be made arbitrarily close to k+ 1: the optimal
diverse-path reservation is almost twice as expensive as the optimal (1; k)-resilient reservation.
As usual, one would expect that the normal situation is even better than suggested by Proposition 10,
and in many practical settings the optimal diverse-path reservation (which can be found easily, as
shown in Section 2.2) will not be very far from the overall optimal solution in cost. Given the
simplicity of a diverse-path solution, it is likely that this is a good solution to adopt.
4 Applications to More than one Source-Destination Pair
We now consider the problem where we are given a collection of node pairs
as a collection of failure rates T i , a collection of integers k Each
commodity i must reserve capacity in a network D which is (T )-resilient for the source-destination
One approach to tackling this problem is to insist on diverse-path reservation vectors. We have
seen that such reservations may cost more, even in the 1-commodity case, but also have several
practical advantages. This approach also allows us to formulate the problem in a similar manner to
the well-known multicommodity capacity allocation problem where there is a flow demand between
each commodity pair and one must find routings of the flow such that capacity cost in the network is
minimized.
Suppose that, for each commodity i, we look for a reservation using j i diverse paths, each with capacity
. If each arc a is equipped with an integer upper bound M a on the total capacity that can be
reserved on a, and a cost c a , then one may pose this as a mixed integer program as follows.
min
a c a y a
a for each arc a
a 2 f0; 1g for each a and i
Of course, there are still many choices of for each commodity, and we must branch on these in
order to find the global optimum.

Acknowledgements

: The research of the first and second authors is supported by the EU-HCM
grant TMRX-CT98 0202 DONET. They would also like to acknowledge support from DIMACS during
extended visits to Bell Labs. Some of the first author's research was also carried out while visiting
the University of Memphis. The authors are grateful for insightful remarks and encouragement from
Gautam Appa, Dan Bienstock, Fan Chung, Michele Conforti, Bharat Doshi, Susan Powell, Paul
Seymour and Mihalis Yannakakis.
A major inspiration for our work on this paper was Dr. Ewart Lowe, of British Telecom, who tragically
died in a diving accident on May 22nd, 1998, off the coast of Normandy. Ewart introduced the authors
to many mathematical problems in telecommunications. He also acted as mentor to the final author
during his projects for British Telecom. We dedicate this paper to the memory of his inspiration,
generosity, and his unbounded enthusiasm which will be greatly missed by all who knew him.



--R

Network Flows - Theory

Capacity and survivability models for telecommunications networks
Combinatorial online optimization in practice
Modeling and solving the single facility line restoration problem
Network design using cut inequalities
Cyclic scheduling via integer programs with circular ones
Minimum cost capacity installation for multicommodity network flows
Capacitated network design - polyhedral structure and computation
Strong inequalities for capacitated survivable network design prob- lems
Some strategies for reserving resilient capacity
Reserving resilient capacity with upper bound constraints
Resilience strategy for a single source-destination pair
An optimal spare-capacity assignment model for survivable networks with hop limits

The directed subgraph homeomorphism problem
Connectivity and network flows
Design of survivable networks

Optimal capacity placement for path restoration in mesh survivable networks
Modelling and solving the capacitated network loading problem
The convex hull of two core capacitated network design problems
Modelling and solving the two facility capacitated network loading problem
Polyhedral properties of the network restoration problem - with the convex hull of a special case Working Paper OR 323-97

Two strategies for spare capacity placement in mesh restorable networks
--TR

--CTR
Friedrich Eisenbrand , Fabrizio Grandoni, An improved approximation algorithm for virtual private network design, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
network flows;resilience;capacity reservation