Engineering Commons^™

Algebraic Approaches To Stochastic Optimization, Katherine Hastings

All Dissertations

The dissertation presents algebraic approaches to the shortest path and maximum flow problems in stochastic networks. The goal of the stochastic shortest path problem is to find the distribution of the shortest path length, while the goal of the stochastic maximum flow problem is to find the distribution of the maximum flow value. In stochastic networks it is common to model arc values (lengths, capacities) as random variables. In this dissertation, we model arc values with discrete non-negative random variables and shows how each arc value can be represented as a polynomial. We then define two algebraic operations and use …