Shortest Path Problem with Cache-Dependent Path Lengths

• Main Authors: FU, Z., Kurnia, A., LIM, Andrew, RODRIGUES, Brian
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2003
• Subjects: Operations and Supply Chain Management
• Online Access: https://ink.library.smu.edu.sg/lkcsb_research/2064; https://doi.org/10.1109/CEC.2003.1299437
• Institution: Singapore Management University

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 heuris...