Date of Award
5-2012
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Legacy Department
Mathematical Science
Committee Chair/Advisor
Shier, Douglas
Committee Member
Fralix , Brian
Committee Member
Matthews , Gretchen
Committee Member
Saltzman , Matthew
Abstract
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 these operations to develop both exact and approximating algorithms for each problem in acyclic networks. Using majorization concepts, we show that the approximating algorithms produce bounds on the distribution of interest; we obtain both lower and upper bounding distributions. We also obtain bounds on the expected shortest path length and expected maximum flow value. In addition, we used fixed-point iteration techniques to extend these approaches to general networks. Finally, we present a modified version of the Quine-McCluskey method for simplification of Boolean expressions in order to simplify polynomials used in our work.
Recommended Citation
Hastings, Katherine, "Algebraic Approaches to Stochastic Optimization" (2012). All Dissertations. 935.
https://tigerprints.clemson.edu/all_dissertations/935