Efficient approximation algorithms for computing k-disjoint minimum cost paths with delay constraint

Abstract

For a given graph G with distinct vertices s, t and a given delay constraint D ∈ R+, the k-disjoint restricted shortest path (kRSP) problem of computing k-disjoint minimum cost stpaths with total delay restrained by D, is known to be NP-hard. Bifactor approximation algorithms have been developed for its special case when k = 2, while no approximation algorithm with constant single factor or bifactor ratio has been developed for general k. This paper firstly presents a (k, (1 + ε)H(k))-approximation algorithm for the kRSP problem by extending Orda's factor(1.5, 1.5) approximation algorithm [9]. Secondly, this paper gives a novel linear programming (LP) formula for the kRSP problem. Based on LP rounding technology, this paper rounds an optimal solution of this formula and obtains an approximation algorithm within a bifactor ratio of (2, 2). To the best of our knowledge, it is the first approximation algorithm with constant bifactor ratio for the kRSP problem. Our results can be applied to serve applications in networks which require quality of service and robustness simultaneously, and also have broad applications in construction of survivable networks and fault tolerance systems.