ICS 269, Fall 2003: Theory Seminar
31 Oct 2003:
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.
The Inverse Shortest Paths Problem with Upper Bounds on Shortest Paths Costs
authored by D. Burton, W.R. Pulleyblank, and Ph.L. Toint
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.