Can I read Optimal Decisions in Stochastic Graphs with Uncorrelated and Correlated Edge Weights on EtoBox?

Optimal Decisions in Stochastic Graphs with Uncorrelated and Correlated Edge Weights by Peter Buchholz; Iryna Dohndorf is a Engineering article available to read on EtoBox.

What is Optimal Decisions in Stochastic Graphs with Uncorrelated and Correlated Edge Weights about?

Stochastic graph models and algorithms for the computation of different stochastic shortest path problems (SSPPs) continue to play an important role in various fields of computer science and operations research, with recent applications ranging from vehicle routing to social networks and decision problems in finance. In this paper, we first introduce stochastic graph models where weights to pass an edge in a graph are, possibly correlated, random variables. Depending on the application context and the interpretation of uncertain edge weights, random variables either model the time to pass an edge or describe a reward one gains by traversing an edge. For modeling the random variables discrete phase type distributions are used. Several algorithms for the computation of optimal policies which depend on the current weight upon arriving at a vertex while still exploiting weight dependencies among edges are developed. It will be shown that with correlated edge weights the stochastic shortest path problems become PSPACE-complete and the solution of instances with a bounded number of phases is NP-hard such that for an exact computation of the shortest path, algorithms from partially observ

Who reads Optimal Decisions in Stochastic Graphs with Uncorrelated and Correlated Edge Weights?

Author

Peter Buchholz; Iryna Dohndorf

Publisher

Elsevier BV

Published

2023

Language

EN

Field

Engineering (Physical Sciences)