TY - GEN

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

AU - Guo, Longkun

AU - Shen, Hong

AU - Liao, Kewen

PY - 2013

Y1 - 2013

N2 - For a given graph G with positive integral cost and delay on edges, distinct vertices s and t, cost bound C â̂̂ Z + and delay bound D â̂̂ Z +, the k bi-constraint path (kBCP) problem is to compute k disjoint st-paths subject to C and D. This problem is known NP-hard, even when k = 1 [4]. 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 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 by setting and a factor-(1.567, 1.567) algorithm by setting. Besides, by setting β = 0, an approximation algorithm with ratio (1, O(ln n)), i.e. an algorithm with only a single factor ratio O(ln n) on cost, can be immediately obtained. To the best of our knowledge, this is the first non-trivial approximation algorithm for the kBCP problem that strictly obeys the delay constraint.

AB - For a given graph G with positive integral cost and delay on edges, distinct vertices s and t, cost bound C â̂̂ Z + and delay bound D â̂̂ Z +, the k bi-constraint path (kBCP) problem is to compute k disjoint st-paths subject to C and D. This problem is known NP-hard, even when k = 1 [4]. 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 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 by setting and a factor-(1.567, 1.567) algorithm by setting. Besides, by setting β = 0, an approximation algorithm with ratio (1, O(ln n)), i.e. an algorithm with only a single factor ratio O(ln n) on cost, can be immediately obtained. To the best of our knowledge, this is the first non-trivial approximation algorithm for the kBCP problem that strictly obeys the delay constraint.

KW - NP-hard

KW - auxiliary graph

KW - bifactor approximation algorithm

KW - cycle cancellation

KW - k-disjoint bi-constraint path

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

U2 - 10.1007/978-3-642-38768-5_30

DO - 10.1007/978-3-642-38768-5_30

M3 - Conference contribution

AN - SCOPUS:84884913787

SN - 9783642387678

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 325

EP - 336

BT - Computing and Combinatorics - 19th International Conference, COCOON 2013, Proceedings

T2 - 19th International Computing and Combinatorics Conference, COCOON 2013

Y2 - 21 June 2013 through 21 June 2013

ER -