Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/108585
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Brief announcement: efficient approximation algorithms for computing k disjoint restricted shortest paths |
Author: | Guo, L. Shen, H. Liao, K. Li, P. |
Citation: | Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures, 2015, vol.2015-June, pp.62-64 |
Publisher: | ACM |
Issue Date: | 2015 |
ISBN: | 9781450335881 |
Conference Name: | 27th ACM symposium on Parallelism in Algorithms and Architectures (SPAA) (13 Jun 2015 - 15 Jun 2015 : Portland, OR) |
Statement of Responsibility: | Longkun Guo, Kewen Liao |
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 ∈ 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. |
Keywords: | k Disjoint Restricted Shortest Path; Bifactor Approximation Algorithm; Auxiliary Graph; Cycle Cancellation. |
Rights: | Copyright is held by the owner/author(s). Publication rights licensed to ACM |
DOI: | 10.1145/2755573.2755608 |
Published version: | http://dx.doi.org/10.1145/2755573.2755608 |
Appears in Collections: | Aurora harvest 3 Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
RA_hdl_108585.pdf Restricted Access | Restricted Access | 334.92 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.