TY - JOUR

T1 - Improved approximation algorithms for computing k disjoint paths subject to two constraints

AU - Guo, Longkun

AU - Shen, Hong

AU - Liao, Kewen

PY - 2015/1

Y1 - 2015/1

N2 - 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.

AB - 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.

KW - Auxiliary graph

KW - Bifactor approximation algorithm

KW - Cycle cancellation

KW - k-disjoint bi-constraint path

KW - NP-hard

UR - http://www.scopus.com/inward/record.url?scp=84920707889&partnerID=8YFLogxK

U2 - 10.1007/s10878-013-9693-x

DO - 10.1007/s10878-013-9693-x

M3 - Article

AN - SCOPUS:84920707889

VL - 29

SP - 153

EP - 164

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

SN - 1382-6905

IS - 1

ER -