# 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.