.png){kind=icon}
.png){kind=icon}
Return
A Fast Hybrid ε-Approximation Algorithm for Computing Constrained Shortest Paths
.png){kind=icon}
PRE
AI
DOI：10.1109/LCOMM.2013.052413.130811.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 epsilon-approximation algorithm is faster than the best known approximation algorithm by one or two orders of magnitude ( depending on the network size and epsilon).
Keywords:
Delay-constrained least cost routing
multi-constrained path
approximation algorithm
heuristic algorithm
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
4.4
Papers:
1.3W
Citations:
2.2W
