TY - GEN

T1 - Brief announcement

T2 - 27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2015

AU - Guo, Longkun

AU - Shen, Hong

AU - Liao, Kewen

AU - Li, Peng

N1 - Publisher Copyright:
Copyright © 2015 ACM.

PY - 2015/6/13

Y1 - 2015/6/13

N2 - Let G = (V, E) be a digraph with nonnegative integral cost and delay on each edge, s and t be two vertices, and D ∈ ℤ+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 pseudopolynomial-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 + ln1/γ)) for any fixed γ > 0 [3, 5]. To the best of our knowledge, this is the first constant-factor algorithm that almost strictly obeys kRSP constraint.

AB - Let G = (V, E) be a digraph with nonnegative integral cost and delay on each edge, s and t be two vertices, and D ∈ ℤ+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 pseudopolynomial-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 + ln1/γ)) for any fixed γ > 0 [3, 5]. To the best of our knowledge, this is the first constant-factor algorithm that almost strictly obeys kRSP constraint.

KW - Auxiliary graph

KW - Bifactor approximation algorithm

KW - Cycle cancellation

KW - K disjoint restricted shortest path

UR - http://www.scopus.com/inward/record.url?scp=84947441218&partnerID=8YFLogxK

U2 - 10.1145/2755573.2755608

DO - 10.1145/2755573.2755608

M3 - Conference contribution

AN - SCOPUS:84947441218

T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures

SP - 62

EP - 64

BT - SPAA 2015 - Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures

PB - Association for Computing Machinery

Y2 - 13 June 2015 through 15 June 2015

ER -