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

Abstract

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
Volume2
StatePublished - Sep 15 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

Keywords

  • Quality of Service (QoS)
  • Routing

Fingerprint 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