A Fast Hybrid ε-Approximation Algorithm for Computing Constrained Shortest Paths

摘要

Considerable efforts have been dedicated to develop both heuristic and approximation algorithms for the NP-complete delay-constrained least-cost (DCLC) routing problem, but to the best of our knowledge, no prior work has been done to mingle the two tracks of research. In this letter we introduce a novel idea to show how a heuristic method can be used to boost the average performance of an approximation algorithm. Simulations on networks of up to 8192 nodes demonstrate that our new hybrid ε-approximation algorithm is faster than the best known approximation algorithm by one or two orders of magnitude (depending on the network size and ε).