Brief announcement : Efficient approximation algorithms for computing k disjoint restricted shortest paths

Let G=(V, E) be a digraph with nonnegative integral cost and delay on each edge, s and t be two vertices, and D ∈ Z+/o be a delay bound, the k disjoint Restricted Shortest Path (k RSP) problem is to compute k disjoint paths between s and t with the total cost minimized and the total delay bounded by D. In this paper, we first present a pseudo-polynomial-time algorithm with a bifactor approximation ratio of (1,2), then improve the algorithm to polynomial time with a bifactor ratio of (1+ε,2+ε) for any fixed ε>0, which is better than the current best approximation ratio (O(1+λ), O(1 + ln 1/λ)) for any fixed λʌ0. To the best of our knowledge, this is the first constant-factor algorithm that almost strictly obeys kRSP constraint.