Enhancing ε-approximation algorithms with the optimal linear scaling factor

Finding a least-cost path subject to a delay constraint in a network is an NP-complete problem and has been extensively studied. Many works reported in the literature tackle this problem by using ε-approximation schemes and scaling techniques, i.e., by mapping link costs into integers or at least discrete numbers, a solution which satisfies the delay constraint and has a cost within a factor of the optimal one, that can be computed with pseudopolynomial 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 factor, we investigate the issue of finding the optimal (the smallest) linear scaling factor to reduce the computational complexities, and propose two algorithms, the optimal linear scaling algorithm (OLSA) and the transformed OLSA. We analytically show that the computational complexities of our proposed algorithms are very low, as compared with those of ε-approximation algorithms. Therefore, incorporating the two algorithms can enhance the ε-approximation algorithms by granting them a practically important capability: self-adaptively picking the optimal linear scaling factors in different networks. As such, ε-approximation algorithms become more flexible and efficient.