Shortest Path Problem with Cache-Dependent Path Lengths
Publication Type
Conference Proceeding Article
Publication Date
12-2003
Abstract
Here, we are motivated by the problem of finding the shortest path in a network when traversing Web pages where cache size determines path length. The shortest path problem with cache-dependent path lengths is shown to be NP-complete. It is a new problem for which we propose several effective heuristics, including a Dijkstra heuristic, genetic algorithms and tabu search.
Discipline
Operations and Supply Chain Management
Research Areas
Operations Management
Publication
CEC 2003: 2003 Congress on Evolutionary Computation: Proceedings: Canberra, Australia, 8-12 December 2003
Volume
4
First Page
2756
Last Page
2761
ISBN
9780780378049
Identifier
10.1109/CEC.2003.1299437
Publisher
IEEE
City or Country
Piscataway, NJ
Citation
FU, Z.; Kurnia, A.; LIM, Andrew; and RODRIGUES, Brian.
Shortest Path Problem with Cache-Dependent Path Lengths. (2003). CEC 2003: 2003 Congress on Evolutionary Computation: Proceedings: Canberra, Australia, 8-12 December 2003. 4, 2756-2761.
Available at: https://ink.library.smu.edu.sg/lkcsb_research/2064
Additional URL
https://doi.org/10.1109/CEC.2003.1299437