We study a problem motivated by a scheme for supporting fast restoration in MPLS and optical networks. In this local restoration
scheme detour paths are set-up a priori and network resources are pre-reserved exclusively for carrying rerouted traffic under
network failures. (i.e. they do not carry any traffic under normal working conditions). The detours are such that failed links
can be bypassed locally from the first node that is upstream from the failures. This local bypass activation from the first
detection point for failures along with the dedication of network resources for handling failures permits very fast recovery
times, a critical requirement for these networks. By allowing sharing of the dedicated resources among different detours the
local restoration scheme results in efficient utilization of the pre-reserved network capacity.
In this paper we are interested in the problem of dedicating the least amount of the currently available network capacity
for protection, while guaranteeing fast restoration to the existing traffic along with any traffic that may be admitted in
the future. We show that the problem is NP-hard, and give a 2-approximation algorithm for the problem. We also show that the
integrality gap of a natural relaxation of our problem is Ω(n), thus establishing that any LP-based approach using this relaxation cannot yield a better approximation algorithm for our
problem.