Improved approximation algorithms for computing k disjoint paths subject to two constraints
Journal article
Guo, Longkun, Shen, Hong and Liao, Kewen. (2015). Improved approximation algorithms for computing k disjoint paths subject to two constraints. Journal of Combinatorial Optimization. 29(1), pp. 153-164. https://doi.org/10.1007/s10878-013-9693-x
Authors | Guo, Longkun, Shen, Hong and Liao, Kewen |
---|---|
Abstract | For a given graph G with distinct vertices s and t, nonnegative integral cost and delay on edges, and positive integral bound C 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(lnn)), i.e. it is an algorithm with only a single factor ratio O(lnn) 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 |
Year | 2015 |
Journal | Journal of Combinatorial Optimization |
Journal citation | 29 (1), pp. 153-164 |
Publisher | Springer |
ISSN | 1382-6905 |
Digital Object Identifier (DOI) | https://doi.org/10.1007/s10878-013-9693-x |
Scopus EID | 2-s2.0-84920707889 |
Research or scholarly | Research |
Page range | 153-164 |
Publisher's version | License All rights reserved File Access Level Controlled |
Output status | Published |
Publication dates | |
06 Dec 2013 | |
Publication process dates | |
Deposited | 09 Aug 2021 |
https://acuresearchbank.acu.edu.au/item/8w8z9/improved-approximation-algorithms-for-computing-k-disjoint-paths-subject-to-two-constraints
Restricted files
Publisher's version
106
total views0
total downloads1
views this month0
downloads this month