Data not found

Best Upgrade Plans for Single and Multiple Source-Destination Pairs

Country : Singapore
Department : Singapore Management University
Project Title : Best Upgrade Plans for Single and Multiple Source-Destination Pairs
Researcher : MOURATIDIS, Kyriakos , Lin, Yimin
Keyword : Numerical Analysis and Scientific Computing , Databases and Information Systems , Computer Sciences , Road network , Resource constraint , Network upgrade
Publisher : Institutional Knowledge at Singapore Management University
Year End : 2015
Identifier : https://ink.library.smu.edu.sg/cgi/viewcontent.cgi?article=3274&context=sis_research , https://ink.library.smu.edu.sg/sis_research/2274
Source : Research Collection School Of Computing and Information Systems
Abstract / Description :

In this paper, we study Resource Constrained Best Upgrade Plan (BUP) computation in road network databases. Consider a transportation network (weighted graph) G where a subset of the edges are upgradable, i.e., for each such edge there is a cost, which if spent, the weight of the edge can be reduced to a specific new value. In the single-pair version of BUP, the input includes a source and a destination in G, and a budget B (resource constraint). The goal is to identify which upgradable edges should be upgraded so that the shortest path distance between source and destination (in the updated network) is minimized, without exceeding the available budget for the upgrade. In the multiple-pair version of BUP, a set Q of source-destination pairs is given, and the problem is to choose for upgrade those edges that lead to the smallest sum of shortest path distances across all pairs in Q, subject to budget constraint B. In addition to transportation networks, the BUP query arises in other domains too, such as telecommunications. We propose a framework for BUP processing and evaluate it with experiments on large, real road networks.

References

MOURATIDIS, Kyriakos,Lin, Yimin. (2015). Best Upgrade Plans for Single and Multiple Source-Destination Pairs.  Singapore: Singapore Management University.
MOURATIDIS, Kyriakos,Lin, Yimin. 2015. "Best Upgrade Plans for Single and Multiple Source-Destination Pairs".  Singapore: Singapore Management University.
MOURATIDIS, Kyriakos,Lin, Yimin. "Best Upgrade Plans for Single and Multiple Source-Destination Pairs."  Singapore: Singapore Management University, 2015. Print.
MOURATIDIS, Kyriakos,Lin, Yimin. Best Upgrade Plans for Single and Multiple Source-Destination Pairs. Singapore: Singapore Management University; 2015.

Export

Share