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

Longkun Guo; Hong Shen; Kewen Liao; Peng Li

doi:10.1145/2755573.2755608

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

Longkun Guo, Hong Shen, Kewen Liao, Peng Li

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

9 Citations (Scopus)

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 ∈ ℤ⁺₀ 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.

Original language	English
Title of host publication	SPAA 2015 - Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures
Publisher	Association for Computing Machinery
Pages	62-64
Number of pages	3
ISBN (Electronic)	9781450335881
DOIs	https://doi.org/10.1145/2755573.2755608
Publication status	Published - 13 Jun 2015
Externally published	Yes
Event	27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2015 - Portland, United States Duration: 13 Jun 2015 → 15 Jun 2015

Publication series

Name	Annual ACM Symposium on Parallelism in Algorithms and Architectures
Volume	2015-June

Conference

Conference	27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2015
Country/Territory	United States
City	Portland
Period	13/06/15 → 15/06/15

Keywords

Auxiliary graph
Bifactor approximation algorithm
Cycle cancellation
K disjoint restricted shortest path

Access to Document

10.1145/2755573.2755608

Cite this

Guo, L., Shen, H., Liao, K., & Li, P. (2015). Brief announcement: Efficient approximation algorithms for computing k disjoint restricted shortest paths. In SPAA 2015 - Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures (pp. 62-64). (Annual ACM Symposium on Parallelism in Algorithms and Architectures; Vol. 2015-June). Association for Computing Machinery. https://doi.org/10.1145/2755573.2755608

Guo, Longkun ; Shen, Hong ; Liao, Kewen et al. / Brief announcement : Efficient approximation algorithms for computing k disjoint restricted shortest paths. SPAA 2015 - Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery, 2015. pp. 62-64 (Annual ACM Symposium on Parallelism in Algorithms and Architectures).

@inproceedings{b3a4d759406648b1a2dab11a2150fcda,

title = "Brief announcement: Efficient approximation algorithms for computing k disjoint restricted shortest paths",

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 ∈ ℤ+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.",

keywords = "Auxiliary graph, Bifactor approximation algorithm, Cycle cancellation, K disjoint restricted shortest path",

author = "Longkun Guo and Hong Shen and Kewen Liao and Peng Li",

note = "Publisher Copyright: Copyright {\textcopyright} 2015 ACM.; 27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2015 ; Conference date: 13-06-2015 Through 15-06-2015",

year = "2015",

month = jun,

day = "13",

doi = "10.1145/2755573.2755608",

language = "English",

series = "Annual ACM Symposium on Parallelism in Algorithms and Architectures",

publisher = "Association for Computing Machinery",

pages = "62--64",

booktitle = "SPAA 2015 - Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures",

}

Guo, L, Shen, H, Liao, K & Li, P 2015, Brief announcement: Efficient approximation algorithms for computing k disjoint restricted shortest paths. in SPAA 2015 - Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures. Annual ACM Symposium on Parallelism in Algorithms and Architectures, vol. 2015-June, Association for Computing Machinery, pp. 62-64, 27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, United States, 13/06/15. https://doi.org/10.1145/2755573.2755608

Brief announcement: Efficient approximation algorithms for computing k disjoint restricted shortest paths. / Guo, Longkun; Shen, Hong; Liao, Kewen et al.
SPAA 2015 - Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery, 2015. p. 62-64 (Annual ACM Symposium on Parallelism in Algorithms and Architectures; Vol. 2015-June).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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

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 -

Guo L, Shen H, Liao K, Li P. Brief announcement: Efficient approximation algorithms for computing k disjoint restricted shortest paths. In SPAA 2015 - Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery. 2015. p. 62-64. (Annual ACM Symposium on Parallelism in Algorithms and Architectures). doi: 10.1145/2755573.2755608

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

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this