Routing with many additive QoS constraints
Guoliang Xue, A. Sen, R. Banka · 2004
A fundamental problem in QoS routing is to find a path between a specified source-destination node pair that satisfies a set of end-to-end quality of service constraints. We study this problem in a communication system where there are multiple additive quality of service parameters associated with each link. It is well-known that the multi-constrained path selection problem (MCPS) is NP-complete. In this paper, we present a fully polynomial time approximation scheme for an optimization version of the MCPS problem. This means that for any given /spl epsi/ > 0, we can compute, in time bounded by a polynomial of the input size of the problem and in 1//spl epsi/, a solution whose cost is at most (1 + /spl epsi/) of that of the optimal solution.