×

zbMATH — the first resource for mathematics

On an instance of the inverse shortest paths problem. (English) Zbl 0756.90089
Summary: The inverse shortest paths problem in a graph is considered, that is, the problem of recovering the arc costs given some information about the shortest paths in the graph. The problem is first motivated by some practical examples arising from applications. An algorithm based on the Goldfarb-Idnani method for convex quadratic programming is then proposed and analyzed for one of the instances of the problem. Preliminary numerical results are reported.

MSC:
90C35 Programming involving graphs or networks
90-08 Computational methods for problems pertaining to operations research and mathematical programming
05C85 Graph algorithms (graph-theoretic aspects)
90C20 Quadratic programming
05C38 Paths and cycles
Software:
ZQPCVX
PDF BibTeX Cite
Full Text: DOI
References:
[1] P.H. Calamai and A.R. Conn, ”A stable algorithm for solving the multifacility location problem involving Euclidian distances,”SIAM Journal on Scientific and Statistical Computing 4 (1980) 512–525. · Zbl 0469.65040
[2] P.H. Calamai and A.R. Conn, ”A second-order method for solving the continuous multifacility location problem,” in: G.A. Watson, ed.,Numerical Analysis: Proceedings of the Ninth Biennial Conference, Dundee, Scotland. Lectures Notes in Mathematics No 912 (Springer, Berlin-Heidelberg-New York, 1982) pp 1–25. · Zbl 0485.65013
[3] P.H. Calamai and A.R. Conn, ”A projected Newton method forl p norm location problem,”Mathematical Programming 38 (1987) 75–109. · Zbl 0642.90035
[4] E.W. Dijkstra, ”A note on two problems in connexion with graphs,”Numerische Mathematik 1 (1959) 269–271. · Zbl 0092.16002
[5] D.B. Johnson, ”Efficient algorithms for shortest paths in sparse networks,”Journal of the Assocation for Computing Machinery 24 (1977) 1–13. · Zbl 0343.68028
[6] J.A. George and J.W. Liu,Computer Solution of Large Positive Definite Systems (Prentice-Hall, Englewood Cliffs, N.J. 1981). · Zbl 0516.65010
[7] D. Goldfarb and A. Idnani, ”A numerically stable dual method for solving strictly convex quadratic programs,”Mathematical Programming 27 (1983) 1–33. · Zbl 0537.90081
[8] G.H. Golub and C.F. van Loan,Matrix Computations (North Oxford Academic, Oxford, 1983). · Zbl 0559.65011
[9] G. Neumann-Denzau and J. Behrens, ”Inversion of seismic data using tomographical reconstruction techniques for investigations of laterally inhomogeneous media,”Geophysical Journal of the Royal Astronomical Society 79 (1984) 305–315.
[10] G. Nolet, ed.,Seismic Tomography (Reidel, Dordrecht, 1987).
[11] M.J.D. Powell, ”On the quadratic programming algorithm of Goldfarb and Idnani,”Mathematical Programming Study 25 (1985) 45–61. · Zbl 0584.90069
[12] M.J.D. Powell, ”ZQPCVX, A Fortran subroutine for convex quadratic programming,” Report DAMTP/NA17, Department of Applied Mathematics and Theoretical Physics, University of Cambridge (Cambridge, UK, 1983).
[13] A. Tarantola,Inverse Problem Theory. Methods for Data Fitting and Model Parameter Estimation (Elsevier, Amsterdam, 1987). · Zbl 0875.65001
[14] R.E. Tarjan, ”Data structures and network algorithms,”CBMS-BSF Conference Series in Applied Mathematics (SIAM, Philadelphia, PA, 1983). · Zbl 0584.68077
[15] J.H. Woodhouse and A.M. Dziewonski, ”Mapping the upper mantle: three-dimensional modeling of Earth structure by inversion of seismic waveforms,”Journal of Geophysical Research 89 (B7) (1984) 5953–5986.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.