Efficient approximation algorithms for computing k disjoint constrained shortest paths

Let be a given directed graph in which every edge e is associated with two nonnegative costs: a weight w(e) and a length l(e). For a pair of specified distinct vertices , the k-(edge) disjoint constrained shortest path (kCSP) problem is to compute k (edge) disjoint paths between s and t, such that the total length of the paths is minimized and the weight is bounded by a given weight budget . The problem is known to be -hard, even when (Garey and Johnson in Computers and intractability, 1979). Approximation algorithms with bifactor ratio and have been developed for in Orda and Sprintson (IEEE INFOCOM, pp. 727-738, 2004) and Chao and Hong (IEICE Trans Inf Syst 90(2):465-472, 2007), respectively. For general k, an approximation algorithm with ratio has been developed for a weaker version of kCSP, the k bi-constraint path problem which is to compute k disjoint st-paths satisfying a given length constraint and a weight constraint simultaneously (Guo et al. in COCOON, pp. 325-336, 2013). This paper first gives an approximation algorithm with bifactor ratio for kCSP using the LP-rounding technique. The algorithm is then improved by adopting a more sophisticated method to round edges. It is shown that for any solution output by the improved algorithm, there exists a real number such that the weight and the length of the solution are bounded by times and times of that of an optimum solution, respectively. The key observation of the ratio proof is to show that the fractional edges, in a basic solution against the proposed linear relaxation of kCSP, exactly compose a graph in which the degree of every vertex is exactly two. At last, by a novel enhancement of the technique in Guo et al. (COCOON, pp. 325-336, 2013), the approximation ratio is further improved to .