IEEE Transactions on Computers · 2011 · 31 citations · 22 references
ComputingComputer ScienceAlgorithmsComputer NetworksTheory Of ComputationApproximation AlgorithmsNetwork OptimizationPropagation DelayFully Polynomial-time Approximation SchemePath SelectionPolynomial Time ComplexityPolynomial-time Approximation SchemeSimple Algorithm
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-ε) 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.
22
A dual algorithm for the constrained shortest path problem
Gabriel Y. Handler, Israël Zang · Networks · 1980 · 454 citations
Algorithms for finding paths with multiple constraints
Jeffrey M. Jaffe · Networks · 1984 · 395 citations