Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/95766
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Journal article |
Title: | Improved approximation algorithms for computing k disjoint paths subject to two constraints |
Author: | Guo, L. Shen, H. Liao, K. |
Citation: | Journal of Combinatorial Optimization, 2015; 29(1):153-164 |
Publisher: | SPRINGER |
Issue Date: | 2015 |
ISSN: | 1382-6905 1573-2886 |
Statement of Responsibility: | Longkun Guo, Hong Shen, Kewen Lia |
Abstract: | For a given graph G with distinct vertices s and t, nonnegative integral cost and delay on edges, and positive integral boundC and D on cost and delay respectively, the k bi-constraint path (kBCP) problem is to compute k disjoint st-paths subject to C and D. This problem is known to be NP-hard, even when k = 1 (Garey and Johnson, Computers and Intractability, 1979 ). This paper first gives a simple approximation algorithm with factor-(2, 2), i.e. the algorithm computes a solution with delay and cost bounded by 2 ∗ D and 2 ∗ C respectively. Later, a novel improved approximation algorithm with ratio (1 + β, max{2, 1 + ln(1/β)}) is developed by constructing interesting auxiliary graphs and employing the cycle cancellation method. As a consequence, we can obtain a factor-(1.369, 2) approximation algorithm immediately and a factor-(1.567, 1.567) algorithm by slightly modifying the algorithm. Besides, when β = 0, the algorithm is shown to be with ratio (1, O(ln n)), i.e. it is an algorithm with only a single factor ratio O(ln n) on cost. To the best of our knowledge, this is the first non-trivial approximation algorithm that strictly obeys the delay constraint for the kBCP problem. |
Keywords: | k-disjoint bi-constraint path; NP-hard; Bifactor approximation algorithm; Auxiliary graph; Cycle cancellation |
Rights: | © Springer Science+Business Media New York 2013 |
DOI: | 10.1007/s10878-013-9693-x |
Published version: | http://dx.doi.org/10.1007/s10878-013-9693-x |
Appears in Collections: | Aurora harvest 7 Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.