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 proceedingConference Paper published in Proceedings

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.

Original languageEnglish
Title of host publicationSPAA 2015 - Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures
PublisherAssociation for Computing Machinery (ACM)
Pages62-64
Number of pages3
Volume2015
ISBN (Electronic)9781450335881
DOIs
Publication statusPublished - 13 Jun 2015
Externally publishedYes
Event27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2015 - Portland, United States
Duration: 13 Jun 201515 Jun 2015

Conference

Conference27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2015
CountryUnited States
CityPortland
Period13/06/1515/06/15

    Fingerprint

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 (Vol. 2015, pp. 62-64). Association for Computing Machinery (ACM). https://doi.org/10.1145/2755573.2755608