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.