Dissertation
A Max-Flow Min-Cut Theorem for Multiple Commodities and Stability of Steinhaus Filtrations
Washington State University
Doctor of Philosophy (PhD), Washington State University
01/2021
DOI:
https://doi.org/10.7273/000005440
Handle:
https://hdl.handle.net/2376/119696
Abstract
The Max-Flow problem is a classic problem in the study of network flows. Its solution, the Max-Flow Min-Cut theorem, is a celebrated duality result which solves this problem and gives rise to several polynomial time solution algorithms. But while we have such fast algorithms for the classical \MaxFlow problem, relatively little attention has been paid to generalizations of this problem into flows of multiple commodities.
In this dissertation we explore a multiple commodity generalization of the \MaxFlow problem in which we study flows composed of real-valued k-vectors through networks with capacities formed by regions in $\mathbb{R}^k$. Unlike the single commodity case the multiple commodity case does not have a clear ordering for flow values. Because of this, we discuss generalizations of max flows to this new setting, ultimately adopting the max flow to be the feasible region of flow values.
We define a collection of concepts and operations, giving us tools to develop an idea of the mutual capacity of a set of cuts, the set of flows which can pass through all cuts in the set. From this, we develop a method to calculate this simply for pairs of cuts, and give a general method of calculation for arbitrary sets of cuts. We show that the mutual capacity is exactly the set of feasible flows in the network, and hence is equal to the max flow.
However, there are some cases which can be solved with a more tractable ordering. We focus on problems in which we search for the maximum multiple of a given vector which can be transported through the network, ultimately producing an algorithm which estimates (or in some cases finds exactly) the maximum multiple.
Finally, we examine a different use of graphs to better understand complex systems: we discuss a generalization of the Mapper algorithm from topological data analysis and show that, unlike the original algorithm, our generalization has a form of stability and hence a quantifiable robustness against noise in the point cloud.
Metrics
5 File views/ downloads
51 Record Views
Details
- Title
- A Max-Flow Min-Cut Theorem for Multiple Commodities and Stability of Steinhaus Filtrations
- Creators
- Matthew Broussard
- Contributors
- Bala Krishnamoorthy (Advisor)Bala Krishnamoorthy (Committee Member)Matthew Huddleson (Committee Member)Judith McDonald (Committee Member)
- Awarding Institution
- Washington State University
- Academic Unit
- Department of Mathematics and Statistics
- Theses and Dissertations
- Doctor of Philosophy (PhD), Washington State University
- Publisher
- Washington State University
- Number of pages
- 109
- Identifiers
- 99900592257601842
- Language
- English
- Resource Type
- Dissertation