Indexed by:
Abstract:
Let G = (V, E) be a digraph with nonnegative integral cost and delay on each edge, s and t be two vertices, and D. epsilon Zeta(+) (0) be a delay bound, the k disjoint Restricted Shortest Path (kRSP) 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+ epsilon, 2+ o) for any fixed epsilon > 0, which is better than the current best approximation ratio (O (1 + gamma), O(1 + ln 1/gamma) for any fixed gamma > 0 [3, 5]. To the best of our knowledge, this is the first constant-factor algorithm that almost strictly obeys kRSP constraint .
Keyword:
Reprint 's Address:
Email:
Version:
Source :
SPAA'15: PROCEEDINGS OF THE 27TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES
Year: 2015
Page: 62-64
Language: English
Cited Count:
WoS CC Cited Count: 8
SCOPUS Cited Count: 9
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: