ICS Theory Group

ICS 269, Fall 2003: Theory Seminar

31 Oct 2003:
The Inverse Shortest Paths Problem with Upper Bounds on Shortest Paths Costs
authored by D. Burton, W.R. Pulleyblank, and Ph.L. Toint

In: P. Pardalos, D. W. Hearn, and W. H. Hager, eds. Network Optimization, Springer Lecture Notes in Economics and Mathematical Systems, 450 (1997), 156-171.

presented by Kevin Wortman

We examine the computational complexity of the inverse shortest paths problem with upper bounds on shortest path costs, and prove that obtaining a globally optimum solution to this problem is NP-complete. An algorithm for finding a locally optimum solution is proposed, discussed and tested.