TY - JOUR

T1 - Computing a most probable delay constrained path

T2 - NP-hardness and approximation schemes

AU - Xiao, Ying

AU - Thulasiraman, Krishnaiya

AU - Fang, Xi

AU - Yang, Dejun

AU - Xue, Guoliang

N1 - Funding Information:
This research was supported in part by ARO grant W911NF-09-1-0467 and US National Science Foundation (NSF) grant CCF-0830739. The information reported here does not reflect the position or the policy of the federal government. All correspondences should be addressed to Guoliang Xue.

PY - 2012

Y1 - 2012

N2 - Delay constrained path selection is concerned with finding a source-to-destination path so that the delay of the path is within a given delay bound. When the network is modeled by a directed graph where the delay of a link is a random variable with a known mean and a known variance, the problem becomes that of computing a most probable delay constrained path. In this paper, we present a comprehensive theoretical study of this problem. First, we prove that the problem is NP-hard. Next, for the case where there exists a source-to-destination path with a delay mean no more than the given delay bound, we present a fully polynomial time approximation scheme. In other words, for any given constant ε such that 0 < ε < 1, our algorithm computes a path whose probability of satisfying the delay constraint is at least (1-\epsilon ) times the probability that the optimal path satisfies the delay constraint, with a time complexity bounded by a polynomial in the number of network nodes and 1/ε. Finally, for the case where any source-to- destination path has a delay mean larger than the given delay bound, we present a simple approximation algorithm with an approximation ratio bounded by the square root of the hop count of the optimal path.

AB - Delay constrained path selection is concerned with finding a source-to-destination path so that the delay of the path is within a given delay bound. When the network is modeled by a directed graph where the delay of a link is a random variable with a known mean and a known variance, the problem becomes that of computing a most probable delay constrained path. In this paper, we present a comprehensive theoretical study of this problem. First, we prove that the problem is NP-hard. Next, for the case where there exists a source-to-destination path with a delay mean no more than the given delay bound, we present a fully polynomial time approximation scheme. In other words, for any given constant ε such that 0 < ε < 1, our algorithm computes a path whose probability of satisfying the delay constraint is at least (1-\epsilon ) times the probability that the optimal path satisfies the delay constraint, with a time complexity bounded by a polynomial in the number of network nodes and 1/ε. Finally, for the case where any source-to- destination path has a delay mean larger than the given delay bound, we present a simple approximation algorithm with an approximation ratio bounded by the square root of the hop count of the optimal path.

KW - Delay constrained path selection

KW - approximation schemes

KW - computational complexity

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

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

U2 - 10.1109/TC.2011.61

DO - 10.1109/TC.2011.61

M3 - Article

AN - SCOPUS:84859713332

SN - 0018-9340

VL - 61

SP - 738

EP - 744

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 5

M1 - 5740849

ER -