TY - JOUR

T1 - Enhancing ε-approximation algorithms with the optimal linear scaling factor

AU - Cheng, Gang

AU - Ansari, Nirwan

AU - Zhu, Li

N1 - Funding Information:
Paper approved by T. T. Lee, the Editor for Switching Systems and Network Performance of the IEEE Communications Society. Manuscript received April 28, 2004; revised February 9, 2006. This work was supported in part by the National Science Foundation under Grant 0435250, and in part by the New Jersey Commission on Science and Technology via NJWINS. This paper was presented in part at the IEEE International Conference on Communications, Seoul, Korea, 2005. G. Cheng is with VPISystems Inc. Corp., Holmdel, NJ 07733 USA.

PY - 2006/9

Y1 - 2006/9

N2 - 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.

AB - 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.

KW - Delay-constrained least cost (DCLC)

KW - Linear scaling factor

KW - NP-complete

KW - ε-approximation

UR - http://www.scopus.com/inward/record.url?scp=33749335844&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33749335844&partnerID=8YFLogxK

U2 - 10.1109/TCOMM.2006.878832

DO - 10.1109/TCOMM.2006.878832

M3 - Article

AN - SCOPUS:33749335844

VL - 54

SP - 1624

EP - 1632

JO - IEEE Transactions on Communications

JF - IEEE Transactions on Communications

SN - 1558-0857

IS - 9

ER -