*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
The Inverse Shortest Path Length Problem (ISPL) is to find the vector of cost coefficients to satisfy given shortest path length constraints in a network. Given a graph and target shortest path length for some oriin and destination pairs, we want a cost vector such that the shortest path length for each given pair will be equal to its target.
The objective of this dissertation is to explore the complexity, algorithms and applications of the Inverse Shortest Path Length Problem (ISPL). Prior researchers showed that ISPL is NP-complete. We explore the complexity of ISPL for special cases. We also introduce some heuristic algorithms and analyze their worst case performance. We test the algorithms on a set of randomly-generated instances, and observe that te results are usually within 3% of optimality. Finally, we present an application of ISPL to telecommunications bandwidth pricing, and test our heuristics on real-world data.
