首页>
外文OA文献
>Brief announcement: efficient approximation algorithms for computing k disjoint restricted shortest paths
【2h】
Brief announcement: efficient approximation algorithms for computing k disjoint restricted shortest paths
展开▼
机译:简要说明:用于计算k个不相交的受限最短路径的有效近似算法
展开▼
免费
页面导航
摘要
著录项
相似文献
相关主题
摘要
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+ 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+∈, 2+∈) for any fixed ǫ > 0, which is better than the current best approximation ratio (O(1 + γ),O(1 + ln ¹ )) for any fixed γ > 0 [3, 5]. To the best of our knowledge, this is the first constant-factor algo- rithm that almost strictly obeys kRSP constraint.
展开▼