Applications of Network Flow
My resource is the original paper by Ford and Fulkerson discussing the concept of max flow through a network. In their paper they define the problem of max network flow, as well as give a proof of the max-flow min-cut theorem. This concept of network flow has gathered the attention of many with many applications and algorithms arising to solve the problem of max flow. Thus, I’ll give a quick definition of what it means to maximize network flow, and then hopefully provide some relation to the concept of trading networks as discussed in class.
Essentially, a flow network consists of a directed graph with nodes and edges linking these nodes. There is a designated source and sink node as part of this network, and every edge has a capacity which is the maximum amount of flow on that edge. Furthermore, every node in the network except the source and sink must satisfy the condition that all of the flow coming into the node has to equal all of the flow coming out of the node. The source is then intuitively where all flow originates from, and the sink is where all flow must finally pass. Thus, we can then consider the concept of a maximum network flow which is the maximum amount of flow that can leave the source and make it’s way to the sink through our network. The max flow min cut theorem then says that the maximum value of a flow in a network flow is equal to the minimum value of a cut in a graph where a cut is a set of edges whose removal would render two separate components of the graph. The value of the cut is merely the sum of the capacities of said edges. Intuitively, this is where we have our bottleneck in the network and can’t push any more flow across this cut. There are many good strongly polynomial time algorithms which makes this a problem that we can solve efficiently. Thus while it can surely be applied to many concepts from the class, we’ll focus on some ways we can use it in trading networks.
For the first application, we consider our trading network consisting of sellers,traders, and buyers. We consider using max flow to determine the maximum amount of goods that can pass from the sellers to the buyers(we’ll leave out the notion of cost for now). This might not seem that useful as for many of the examples from class, it was very clear how many goods could travel through our network. However, as with many things, one can imagine scenarios with thousands or millions of sellers, traders, and buyers. Thus, we could then efficiently compute how many goods can flow across the network which could be useful to know as we can see how effective placement of traders in a network are. Maybe this would allow a company to adjust the placement of their traders so that they can better optimize the flow of goods through the network. Furthermore, we also know the value of the min cut in this network, and there exists other good algorithms for finding this cut. Thus, we can figure out where the bottleneck in the network exists. Maybe as trading organization we would then add in traders to open up to take advantage of this bottleneck. Sellers could also use this information as they might not want to enter a network if the min cut happens across edges traveling to buyers as this would imply that there is less demand than supply. Thus, there are clearly many ways to apply the concepts of network flow to gain information about a trading network. Plus, there are many other more complex formulations of the flow problem that could take into account cost for routing through a trading network that could also be applied. One can see that the concept of flow in network is very naturally applicable to the trading scenario as there is this potential flow of goods.
http://www.cs.yale.edu/homes/lans/readings/routing/ford-max_flow-1956.pdf
– Acerbus Hospes