Enhancing ε-approximation algorithms with the optimal linear scaling factor

Gang Cheng, Nirwan Ansari, Li Zhu

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)1624-1632
Number of pages9
JournalIEEE Transactions on Communications
Issue number9
StatePublished - Sep 2006

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering


  • Delay-constrained least cost (DCLC)
  • Linear scaling factor
  • NP-complete
  • ε-approximation


Dive into the research topics of 'Enhancing ε-approximation algorithms with the optimal linear scaling factor'. Together they form a unique fingerprint.

Cite this