Literature by the same author
plus at Google Scholar

Bibliografische Daten exportieren
 

An efficient algorithm for perturbed shortest path problems

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

Official URL: Volltext

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