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

Gang Cheng, Nirwan Ansari, Li Zhu

Research output: Contribution to journalConference articlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)866-870
Number of pages5
JournalIEEE International Conference on Communications
StatePublished - 2005
Event2005 IEEE International Conference on Communications, ICC 2005 - Seoul, Korea, Republic of
Duration: May 16 2005May 20 2005

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Electrical and Electronic Engineering


  • Quality of Service (QoS)
  • Routing


Dive into the research topics of 'A framework for finding the optimal linear scaling factor of ε-approximation solutions'. Together they form a unique fingerprint.

Cite this