Please use this identifier to cite or link to this item:
http://hdl.handle.net/2440/83728
Citations  
Scopus  Web of Science®  Altmetric 

?

?

Type:  Conference paper 
Title:  Improved approximation algorithms for computing k disjoint paths subject to two constraints 
Author:  Guo, L. Shen, H. Liao, K. 
Citation:  Proceedings of the 19th International Computing and Combinatorics Conference, COCOON 2013, 2013, Hangzhou, China, June 2123, 2013 / D.Z. Du, G. Zhang (eds.), pp.325336 
Publisher:  Springer 
Publisher Place:  Germany 
Issue Date:  2013 
Series/Report no.:  Lecture Notes in Computer Science 
ISBN:  9783642387678 
ISSN:  03029743 16113349 
Conference Name:  International Computing and Combinatorics Conference (19th : 2013 : Hangzhou) 
Statement of Responsibility:  Longkun Guo, Hong Shen, and Kewen Liao 
Abstract:  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 biconstraint path (kBCP) problem is to compute k disjoint stpaths subject to C and D. This problem is known NPhard, 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 (1+β,max{2,1+ln1β}) 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 1+ln1β=2 and a factor(1.567, 1.567) algorithm by setting 1+β=1+ln1β . 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 nontrivial approximation algorithm for the kBCP problem that strictly obeys the delay constraint. 
Keywords:  kdisjoint biconstraint path; NPhard; bifactor approximation algorithm; auxiliary graph; cycle cancellation 
Rights:  © SpringerVerlag Berlin Heidelberg 2013 
RMID:  0020131865 
DOI:  10.1007/9783642387685_30 
Appears in Collections:  Computer Science publications 
Files in This Item:
File  Description  Size  Format  

RA_hdl_83728.pdf  Restricted Access  343.4 kB  Adobe PDF  View/Open 
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.