#algorithm discussion continued
Today we continue reading the flow networks. We were looking at maximum flows
Another lemma bounds the number of non-saturating pushes as less than four times V^2 times the sum of vertex and edge counts taken together. While the relabel and saturating pushes increase the heights, the non-saturating pushes decreases it by at least one. We use their respective bounds to set the bound on non-saturating pushes.
Let us assume a potential function pi which is the sum of the heights of all vertices that have an excess flow.
During the relabel operation of a vertex i, its height cannot increase more than the max height which is two times V minus one. During the saturating push, the heights dont change and only the vertex v with max height 2 times v mimus one can become overflowing.
In both cases, the increase in potential is less than two times V.
The relabel happens at most 2 V^2 times and the saturating push happens at most 2 (VE) times. The total increase in potential is less than 4V^2(V+E).
u was overflowing before the non-saturating push and v may or may not have been overflowing. After the push, u is no longer overflowing and unless v is the source, it may or may not be overflowing. The potential has decreased by u.h and it has increased by 0 or v.h. Since u.h = v.h + 1, this potential decreases by at least one for a non-saturating push
Since potential is greater than 0, the total amount of decrease or the total number of saturating pushes must be less than 4V^2(V+E).
The bounds of each operation taken individually bounds the number of iterations of the generic-push-relabel algorithm.
#codingexercise
Bool ismorethan(node tree1, node tree2)
{
if (tree1 == null && tree2 == null) return true;
if (tree1 == null || tree2 == null) return false:
if(tree1.data <= tree2.data) return false;
Return ismorethan(tree1.left, tree2.left) && ismorethan(tree1.right, tree2.right);
}
#puzzle
How many k tuples of non-negative integer are there that sum upto n if we are given n and k as positive integers.
The answer is the binomial coefficient n+k-1 choose k-1. This is the same as the other binomial coefficient n+k-1 choose n
Today we continue reading the flow networks. We were looking at maximum flows
Maximum flows can also be calculated using "push-relabel" method.
This method performs two basic operations: pushing flow excess from a vertex to one of its neighbors and relabeling a vertex.
The generic-push-relabel method is as follows:
Initialize-Preflow(G, s)
while there exists an applicable push or relabel operation
select an applicable push or relabel operation and perform it.
the generic push relabel algorithm guarantees maximum flow because
The intialization step creates a preflow.
The progress of the algorithm maintains the preflow.
At termination, there are no overflowing vertices and this preflow is a valid flow and there is no path in the residual network. Consequently, the flow is maximum.
We know that the push relabel method indeed terminates because there is a bound on the number of operations it performs. We bound separately each of the three types of operations - relabels, saturating pushes, and non-saturating pushes. With these bounds, the algorithm runs in O(V^2E) time
We use the following lemmas to calculate the bound:
For any overflowing vertex x, there is a simple path from x to source s in the residual network Gf. We prove this by contradiction. If the source is not in the paths to x, then there are two partitions of the overall vertices, one with the source and no path to x and the other opposite. The excess at the vertex x is the sum of the flow outbound - sum of the flow inbound which applies to both partitions. The excess can therefore be calculated by reordering the flows to read as the sum of the flow outbound from both partitions - sum of the flow inbound to both partitions. Since the excess is positive, the sum of the flow outbound has to be greater than zero which implies that there must be residual edge and consequently a simple path from x to that edge's destination vertex, thus contradicting the definition of the partition we made.
The next lemma is also used to calculate the bound.
At any time during the execution of the generic-push-relabel method, we have the height of a source vertex as less than two times the total number of vertices in the network V minus one.
This is easy to prove because the source and destination heights are set and do not change. Moreover they are both less than quoted number in the lemma. When a vertex is relabeled, it is overflowing and has a simple path from that vertex to source in the original network. This puts its height to range from 0 to V minus 1. But for each of those values we have a residual edge that is one level down and adding the height of the vertices we get 2 times V minus one.
The lemma bounds the height of the vertices. Its corollary bounds the number of relabel operations performed in total. The relabel operation is V minus two times the maximum number of relabels per vertex which is given by the lemma as 2 times V minus one. The proof is straightforward because each relabel increases the height of a vertex and the height is bounded for every vertex.
The other operation is the saturating pushes. There is a lemma to bound the saturating pushes to be less than two times the product V E. This is easy to see because if there are any saturating pushes between vertices u and v, at least one direction is an edge in E and if a push has occurred another push cannot happen until the height of u increases by two as the flow is one level down. Also the max height is bounded as two times V minus one. So the height has to be less than two times V and considering this for all edges, we have the quoted product in the lemma.
The generic-push-relabel method is as follows:
Initialize-Preflow(G, s)
while there exists an applicable push or relabel operation
select an applicable push or relabel operation and perform it.
the generic push relabel algorithm guarantees maximum flow because
The intialization step creates a preflow.
The progress of the algorithm maintains the preflow.
At termination, there are no overflowing vertices and this preflow is a valid flow and there is no path in the residual network. Consequently, the flow is maximum.
We know that the push relabel method indeed terminates because there is a bound on the number of operations it performs. We bound separately each of the three types of operations - relabels, saturating pushes, and non-saturating pushes. With these bounds, the algorithm runs in O(V^2E) time
We use the following lemmas to calculate the bound:
For any overflowing vertex x, there is a simple path from x to source s in the residual network Gf. We prove this by contradiction. If the source is not in the paths to x, then there are two partitions of the overall vertices, one with the source and no path to x and the other opposite. The excess at the vertex x is the sum of the flow outbound - sum of the flow inbound which applies to both partitions. The excess can therefore be calculated by reordering the flows to read as the sum of the flow outbound from both partitions - sum of the flow inbound to both partitions. Since the excess is positive, the sum of the flow outbound has to be greater than zero which implies that there must be residual edge and consequently a simple path from x to that edge's destination vertex, thus contradicting the definition of the partition we made.
The next lemma is also used to calculate the bound.
At any time during the execution of the generic-push-relabel method, we have the height of a source vertex as less than two times the total number of vertices in the network V minus one.
This is easy to prove because the source and destination heights are set and do not change. Moreover they are both less than quoted number in the lemma. When a vertex is relabeled, it is overflowing and has a simple path from that vertex to source in the original network. This puts its height to range from 0 to V minus 1. But for each of those values we have a residual edge that is one level down and adding the height of the vertices we get 2 times V minus one.
The lemma bounds the height of the vertices. Its corollary bounds the number of relabel operations performed in total. The relabel operation is V minus two times the maximum number of relabels per vertex which is given by the lemma as 2 times V minus one. The proof is straightforward because each relabel increases the height of a vertex and the height is bounded for every vertex.
The other operation is the saturating pushes. There is a lemma to bound the saturating pushes to be less than two times the product V E. This is easy to see because if there are any saturating pushes between vertices u and v, at least one direction is an edge in E and if a push has occurred another push cannot happen until the height of u increases by two as the flow is one level down. Also the max height is bounded as two times V minus one. So the height has to be less than two times V and considering this for all edges, we have the quoted product in the lemma.
Let us assume a potential function pi which is the sum of the heights of all vertices that have an excess flow.
During the relabel operation of a vertex i, its height cannot increase more than the max height which is two times V minus one. During the saturating push, the heights dont change and only the vertex v with max height 2 times v mimus one can become overflowing.
In both cases, the increase in potential is less than two times V.
The relabel happens at most 2 V^2 times and the saturating push happens at most 2 (VE) times. The total increase in potential is less than 4V^2(V+E).
u was overflowing before the non-saturating push and v may or may not have been overflowing. After the push, u is no longer overflowing and unless v is the source, it may or may not be overflowing. The potential has decreased by u.h and it has increased by 0 or v.h. Since u.h = v.h + 1, this potential decreases by at least one for a non-saturating push
Since potential is greater than 0, the total amount of decrease or the total number of saturating pushes must be less than 4V^2(V+E).
The bounds of each operation taken individually bounds the number of iterations of the generic-push-relabel algorithm.
#codingexercise
Bool ismorethan(node tree1, node tree2)
{
if (tree1 == null && tree2 == null) return true;
if (tree1 == null || tree2 == null) return false:
if(tree1.data <= tree2.data) return false;
Return ismorethan(tree1.left, tree2.left) && ismorethan(tree1.right, tree2.right);
}
#puzzle
How many k tuples of non-negative integer are there that sum upto n if we are given n and k as positive integers.
The answer is the binomial coefficient n+k-1 choose k-1. This is the same as the other binomial coefficient n+k-1 choose n
No comments:
Post a Comment