Please use this identifier to cite or link to this item:
|Scopus||Web of Science®||Altmetric|
|Title:||Efficient approximation algorithms for computing k-disjoint minimum cost paths with delay constraint|
|Citation:||Proceedings, 13th International Conference on Parallel and Distributed Computing, Applications, and Technologies, PDCAT 2012, 2012 / Shen, H., Sang, Y., Li, Y., Qian, D., Zomaya, A. (ed./s), pp.627-631|
|Conference Name:||13th International Conference on Parallel and Distributed Computing, Applications, and Technologies (PDCAT 2012) (14 Dec 2012 - 16 Dec 2012 : Beijing, China)|
|Longkun Guo, Hong Shen|
|Abstract:||For a given graph G with distinct vertices s, t and a given delay constraint D ∈ R+, the k-disjoint restricted shortest path (kRSP) problem of computing k-disjoint minimum cost stpaths with total delay restrained by D, is known to be NP-hard. Bifactor approximation algorithms have been developed for its special case when k = 2, while no approximation algorithm with constant single factor or bifactor ratio has been developed for general k. This paper firstly presents a (k, (1 + ε)H(k))-approximation algorithm for the kRSP problem by extending Orda's factor(1.5, 1.5) approximation algorithm . Secondly, this paper gives a novel linear programming (LP) formula for the kRSP problem. Based on LP rounding technology, this paper rounds an optimal solution of this formula and obtains an approximation algorithm within a bifactor ratio of (2, 2). To the best of our knowledge, it is the first approximation algorithm with constant bifactor ratio for the kRSP problem. Our results can be applied to serve applications in networks which require quality of service and robustness simultaneously, and also have broad applications in construction of survivable networks and fault tolerance systems.|
|Keywords:||k-disjoint restricted shortest path problem; NP-hard; bifactor approximation algorithm; LP rounding|
|Rights:||© 2012 IEEE|
|Appears in Collections:||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.