Title data
Grüne, Lars ; Junge, Oliver:
An efficient algorithm for perturbed shortest path problems.
In: Proceedings in Applied Mathematics and Mechanics.
Vol. 7
(2007)
Issue 1
.
- pp. 1025003-1025004.
ISSN 1617-7061
DOI: https://doi.org/10.1002/pamm.200700714
Abstract in another language
We present an efficient algorithm for perturbed shortest paths problems that arise, e.g., in dynamic games. Via a min-max version of Dijkstra's algorithm we compute piecewise constant upper and lower bounds on the upper value function of the game. Convergence of the bounds in the limit of vanishing cell diameter can be proved. The method is numerically demonstrated on a simple 2d dynamic game, the homicidal chauffeur.
Further data
Item Type: | Article in a journal |
---|---|
Refereed: | Yes |
Institutions of the University: | Faculties Faculties > Faculty of Mathematics, Physics und Computer Science Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematics V (Applied Mathematics) Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematics V (Applied Mathematics) > Chair Mathematics V (Applied Mathematics) - Univ.-Prof. Dr. Lars Grüne |
Result of work at the UBT: | Yes |
DDC Subjects: | 500 Science 500 Science > 510 Mathematics |
Date Deposited: | 03 Mar 2021 12:36 |
Last Modified: | 02 Sep 2022 09:33 |
URI: | https://eref.uni-bayreuth.de/id/eprint/63630 |