Approximation and heuristic algorithms for delay constrained path selection under inaccurate state information

Given a communication network modeled as a directed graph with a delay parameter associated with each link, we consider the problem of determining the most probable delay constrained path from a source node to a destination node. Assuming that the link delays are random variables with continuous and differentiable probability density function and using the central limit theorem this problem can be formulated as a path problem which involves simultaneously optimizing two additive path parameters. Two cases arise. When there is one path with mean delay less than the delay bound, we present an exact pseudo polynomial algorithm, a fully polynomial time ε-approximation algorithm and a strongly polynomial heuristic algorithm. In the unlikely case when this assumption is violated, the problem is shown to be NP-hard and no constant factor approximation algorithm exists if P ≠ NP. We also study the path protection problem under inaccurate state information.