A framework for finding the optimal linear scaling factor of ε-approximation solutions

Many works reported in the literature tackle the problem of delay constrained least cost path selection (DCLC) by using ε-approximation schemes and scaling techniques, i.e., by mapping link costs into integers or, at least, discrete numbers, a solution that satisfies the delay constraint and has a cost within a factor of (1 + ε) of the optimal one can be computed with pseudo polynomial computational complexity. In this paper, having observed that the computational complexities of the ε-approximation algorithms using the linear scaling technique are linearly proportional to the linear scaling factors, we investigate the issue of finding the optimal (the smallest) linear scaling factor to reduce the computational complexities and propose a theoretical framework.