Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Efficient approximation algorithms for computing k-disjoint minimum cost paths with delay constraint
Author: Guo, L.
Shen, H.
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
Publisher: IEEE
Issue Date: 2012
ISBN: 9780769548791
Conference Name: 13th International Conference on Parallel and Distributed Computing, Applications, and Technologies (PDCAT 2012) (14 Dec 2012 - 16 Dec 2012 : Beijing, China)
Statement of
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 [9]. 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
RMID: 0030008046
DOI: 10.1109/PDCAT.2012.69
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.