Shortest Path Problem with Cache-Dependent Path Lengths

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

Full description

Saved in:

Bibliographic Details
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
Tags:	Add Tag No Tags, Be the first to tag this record!
Institution:	Singapore Management University
Language:	English

id	sg-smu-ink.lkcsb_research-3063
record_format	dspace
spelling	sg-smu-ink.lkcsb_research-30632016-03-11T06:14:09Z Shortest Path Problem with Cache-Dependent Path Lengths FU, Z. Kurnia, A. LIM, Andrew RODRIGUES, Brian 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. 2003-12-01T08:00:00Z text https://ink.library.smu.edu.sg/lkcsb_research/2064 info:doi/10.1109/CEC.2003.1299437 https://doi.org/10.1109/CEC.2003.1299437 Research Collection Lee Kong Chian School Of Business eng Institutional Knowledge at Singapore Management University Operations and Supply Chain Management
institution	Singapore Management University
building	SMU Libraries
continent	Asia
country	Singapore Singapore
content_provider	SMU Libraries
collection	InK@SMU
language	English
topic	Operations and Supply Chain Management
spellingShingle	Operations and Supply Chain Management FU, Z. Kurnia, A. LIM, Andrew RODRIGUES, Brian Shortest Path Problem with Cache-Dependent Path Lengths
description	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.
format	text
author	FU, Z. Kurnia, A. LIM, Andrew RODRIGUES, Brian
author_facet	FU, Z. Kurnia, A. LIM, Andrew RODRIGUES, Brian
author_sort	FU, Z.
title	Shortest Path Problem with Cache-Dependent Path Lengths
title_short	Shortest Path Problem with Cache-Dependent Path Lengths
title_full	Shortest Path Problem with Cache-Dependent Path Lengths
title_fullStr	Shortest Path Problem with Cache-Dependent Path Lengths
title_full_unstemmed	Shortest Path Problem with Cache-Dependent Path Lengths
title_sort	shortest path problem with cache-dependent path lengths
publisher	Institutional Knowledge at Singapore Management University
publishDate	2003
url	https://ink.library.smu.edu.sg/lkcsb_research/2064 https://doi.org/10.1109/CEC.2003.1299437
_version_	1770570120193638400

Shortest Path Problem with Cache-Dependent Path Lengths

Similar Items