Efficient approximation algorithms for computing k disjoint constrained shortest paths

Let $$G=(V,\, E)$$ G = ( V , E ) 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 $$s,\, t\in V$$ s , t ∈ V , 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 $$W\in \mathbb {R}_{0}^{+}$$ W ∈ R 0 + . The problem is known to be $${\mathcal {NP}}$$ NP -hard, even when $$k=1$$ k = 1 (Garey and Johnson in Computers and intractability, 1979). Approximation algorithms with bifactor ratio $$\left( 1\,+\,\frac{1}{r},\, r\left( 1\,+\,\frac{2(\log r\,+\,1)}{r}\right) (1\,+\,\epsilon )\right) $$ 1 + 1 r , r 1 + 2 ( log r + 1 ) r ( 1 + ϵ ) and $$(1\,+\,\frac{1}{r},\,1\,+\,r)$$ ( 1 + 1 r , 1 + r ) have been developed for $$k=2$$ k = 2 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 $$(1,\, O(\ln n))$$ ( 1 , O ( ln n ) ) 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 $$(2,\,2)$$ ( 2 , 2 ) 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 $$0\le \alpha \le 2$$ 0 ≤ α ≤ 2 such that the weight and the length of the solution are bounded by $$\alpha $$ α times and $$2-\alpha $$ 2 - α 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 $$(1,\,\ln n)$$ ( 1 , ln n ) .