Thesis Defense :: On the Inverse Shortest Path Length Problem

Event Details
  • Date/Time:
    • Thursday October 16, 2003
      11:00 am - 11:59 pm
  • Location: Groseclose, 226A
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
Barbara Christopher
Industrial and Systems Engineering
Contact Barbara Christopher

Summary Sentence: Thesis Defense :: On the Inverse Shortest Path Length Problem

Full Summary: Thesis Defense :: On the Inverse Shortest Path Length Problem

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.

Additional Information

In Campus Calendar

School of Industrial and Systems Engineering (ISYE)

Invited Audience
No audiences were selected.
No keywords were submitted.
  • Created By: Barbara Christopher
  • Workflow Status: Published
  • Created On: Oct 8, 2010 - 7:42am
  • Last Updated: Oct 7, 2016 - 9:52pm