Brief announcement: efficient approximation algorithms for computing k disjoint restricted shortest paths
| dc.contributor.author | Guo, L. | |
| dc.contributor.author | Shen, H. | |
| dc.contributor.author | Liao, K. | |
| dc.contributor.author | Li, P. | |
| dc.contributor.conference | 27th ACM symposium on Parallelism in Algorithms and Architectures (SPAA) (13 Jun 2015 - 15 Jun 2015 : Portland, OR) | |
| dc.date.issued | 2015 | |
| dc.description.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. | |
| dc.description.statementofresponsibility | Longkun Guo, Kewen Liao | |
| dc.identifier.citation | Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures, 2015, vol.2015-June, pp.62-64 | |
| dc.identifier.doi | 10.1145/2755573.2755608 | |
| dc.identifier.isbn | 9781450335881 | |
| dc.identifier.orcid | Shen, H. [0000-0002-3663-6591] [0000-0003-0649-0648] | |
| dc.identifier.uri | http://hdl.handle.net/2440/108585 | |
| dc.language.iso | en | |
| dc.publisher | ACM | |
| dc.rights | Copyright is held by the owner/author(s). Publication rights licensed to ACM | |
| dc.source.uri | https://doi.org/10.1145/2755573.2755608 | |
| dc.subject | k Disjoint Restricted Shortest Path; Bifactor Approximation Algorithm; Auxiliary Graph; Cycle Cancellation. | |
| dc.title | Brief announcement: efficient approximation algorithms for computing k disjoint restricted shortest paths | |
| dc.type | Conference paper | |
| pubs.publication-status | Published |
Files
Original bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- RA_hdl_108585.pdf
- Size:
- 334.92 KB
- Format:
- Adobe Portable Document Format
- Description:
- Restricted Access