TY - GEN

T1 - Efficient approximation algorithms for computing k-disjoint minimum cost paths with delay constraint

AU - Guo, Longkun

AU - Shen, Hong

PY - 2012

Y1 - 2012

N2 - For a given graph $G$ with distinct vertices $s, \, t$ and a given delay constraint $D\in R^{+}$, the $k$-disjoint restricted shortest path ($k$RSP) problem of computing $k$-disjoint minimum cost $st$-paths 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+\epsilon)H(k))$-approximation algorithm for the $k$RSP problem by extending Orda's factor-$(1.5, \, 1.5)$ approximation algorithm \cite{orda2004efficient}. Secondly, this paper gives a novel linear programming (LP) formula for the $k$RSP 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 $k$RSP 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.

AB - For a given graph $G$ with distinct vertices $s, \, t$ and a given delay constraint $D\in R^{+}$, the $k$-disjoint restricted shortest path ($k$RSP) problem of computing $k$-disjoint minimum cost $st$-paths 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+\epsilon)H(k))$-approximation algorithm for the $k$RSP problem by extending Orda's factor-$(1.5, \, 1.5)$ approximation algorithm \cite{orda2004efficient}. Secondly, this paper gives a novel linear programming (LP) formula for the $k$RSP 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 $k$RSP 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.

KW - LP rounding

KW - NPhard

KW - bifactor approximation algorithm

KW - k-disjoint restricted shortest path problem

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

U2 - 10.1109/PDCAT.2012.69

DO - 10.1109/PDCAT.2012.69

M3 - Conference contribution

AN - SCOPUS:84884622829

SN - 9780769548791

T3 - Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings

SP - 627

EP - 631

BT - Proceedings - 13th International Conference on Parallel and Distributed Computing, Applications, and Technologies, PDCAT 2012

T2 - 13th International Conference on Parallel and Distributed Computing, Applications, and Technologies, PDCAT 2012

Y2 - 14 December 2012 through 16 December 2012

ER -