Greedy techniques iteratively construct an optimal solution by building optimal solutions from smaller problems. Iterative improvement techniques build an optimal solution by iterative refinement of a feasible solution for the complete problem.
Feasible solutions are solutions that satisfy the constraints of the problem, for example using the denominations in the making change problem.
The objective function is the function that problem seeks to maximize or minimize.
Iterative improvement is frequently used in numerical problems, for example root finding or finding the maximum of a function. We will concentrate on iterative improve to graph problems.
Iterative improvements have difficulties:
1. Finding the initial solution (guess to the solution) can be easy, for example the empty set, or on the other hand it can be difficult.
2. The algorithm for refinements the guess may be difficult. The refinement must remain feasible and improve the objective function. Meaning they should not jump around and possibly diverge from the optimal solution.
3. The refinement may find a local optimal solution but not the global optimal solution, for example find the maximum by always going up hill.
The maximum-flow problem seeks a maximum flow in a network (for example of pipes).
A network is a weighted directed graph with n vertices labeled 1, 2, ... , n.
The edges of are typically labeled, (i, j), where i is the index of the origin and j is the destination. The weights, uij or u(i, j), of the edge are positive and typically called the capacity of edge.
The weighted digraph has a single source and sink. A source is a node with only out-going edges and a sink has only in-coming edges. The source vertex is labeled 1 and the sink labeled n.
Draw an example on the board.
A flow, F, in the network is a labeling of the edges with positive values less than the capacity of the edge, cij ≥ xji ≥ 0, such that it satisfy the flow-conservation requirement at all vertices (i), meaning
∑j: (j, i)εE xji = ∑ j: (i, j)εE xij
for i = 2, 3, ..., n-2
total incoming flow = total outgoing flow
Because of flow conservation the total outgoing flow at the source must equal the incoming flow at sink
∑j: (j, n)εE xjn = ∑ j: (1, j)εE xj1 = x, called the flow.
incoming flow at sink = outgoing flow at the source
List examples of Networks and Flows
We will seek the iterative solution by flow augmenting, meaning adding to the current flow. As part of this process we will need to find an augmenting path.
We cannot consider only adding positive values to the flow at each edge because this might miss the optimal solution even if it satisfies flow conservation and does not exceed the capacity. Adding only positive flow values would amount to a greedy approach.
Give an example that shows that an optimal solution is missed.
We need to decrease the flow into one vertex in order to increase the flow into another vertex. Adding a negative flow value would amount to decreasing the flow at a vertex.
We consider paths from the source to sink in the underlying undirected graph of the network. In which each edge of the path (i, j) is either a
1. Forward edge, meaning (i, j) are in the direction of the directed edge of the network. The remaining capacity is rij = uij - xij is the amount that the flow can be increase in that edge.
2. Backward edge, meaning (i, j) is the reverse direction of the directed edge of the network. In other words (j, i) is a directed edge in the network. The remaining capacity (not really the best term in this case) is rij = xij, the current flow. It is the maximum that the flow can be decreased in that edge.
Let r be the minimal of the remaining capacity
r = min(i, j)εP (rij)
where P is the augmented path
We then augmented flow is F' = F + P, where we increase the flow on forward edges by r and decrease the flow on backward edges by r.
It is easy to see that the augmented flow does not exceed the capacity of the edges. The improved flow also satisfies flow conservation at each node. Consider intermediate node, i, in the augmented path. Because the augmentation is a path there are four possible combinations of forward and backward edges
+r → i +r →, +r → i ← -r, -r ← i +r →, -r← i - r ←
where +r represents a forward edge and -r represents a backward edge, and → i is an incoming edge and ← i is an outgoing edge
It is clear that the augmentation is flow conservative. If the original flow satisfy flow conservation so does the augmented flow. So the improved flow is a feasible solution.
Also clear that the augmented flow increases the total flow, so improves the flow. If the all capacities are integers or discrete values, then iterative improvement must halt if there is a bounded solution. We'll prove that the solution is bounded later.
Algorithm Ford-Fulkerson(G)
for each (i, j) in E do xij ← 0 // initial guess flow
do
find path, P, from source to sink // using modified graph transversal
// during the search we mark the edge with forward or backward at cost O(1)
r ← ∞
for each edge (i, j) in P do
if (i, j) is forward then rij ← uij - xij
else
rij
← xij // backward edge
r ← min(r, rij)
if (r > 0) then // improvement possible
for each edge in P do
if (i, j) is forward then
xij ← xij + r
else // backward edges
xij ← xij - r
until r ≤ 0
return xij
Finding an augmented path can be done using DFS or BFS, but to insure that algorithm progresses the algorithm do should not traverse all incident edges in the undirected graph, rather the algorithm should only traverse incident edges such that
1. Outgoing edges with flow less than the capacity
2. Incoming edges with flow
Finding the path takes Θ(n+m), where n is the vertices and m the number of edges
The size of P is at most O(m). Each for loop runs O(m) times and each iteration cost O(1), so the total cost for the for loops is O(m)
So each iteration of the do-until loop cost is at most O(m+n).
The remaining question is how many times does the do-until loop run?
Illustration the example of the bad path algorithm.
So the do-until loop can run max(uij)
The cost is at least O(max(uij)(n+ m)).
For an adjacent list and connected graph, n = O(m).
The cost is then O(max(uij)m).
This is not a good circumstance. It is pseudo polynomial time.
Recall that the BFS is implemented with a queue. Besides labeling forward and back we could label the vertex with its predecessor in the path and the amount of additional flow from the source. The labeling and use of the queue enables writing the algorithm using a single while loop.
Algorithm Edmonds-Karp(G)
make the undi-graph of G
for each (i, j) in E do xij ← 0 // initial guess flow
label source with ∞, -
enqueue(Q, source)
while not Empty(Q) do
i ← Front(Q)
for each edge (i, j) in the undi-graph of G do
if j is unlabelled then // not visited
if (i, j) is forward then
rij ← uij - xij
if rij > 0 then
lj ← min(li, rij)
label j with lj, i+
else // backward edges
if xij > 0 then
lj ← min(li, xij)
label j with lj, i+
Equeue(Q, j)
if sink is labeled then // augmented path found
j ← n // start at the sink
while j ≠ 1 do
if the second label of j is i+ then // forward edge
xij ← xij + ln // Note that ln is the minimal residual
else // backward edge
xij ← xij - ln
j ← i // move backwards along the path
erase all the vertex labels except for the source
reinitialize Q with the source
return xij
Illustrate the solution
A cut is set of edges defined by a partition of the vertices of the network into two sets, where one set X contains the source and the other V-X contains the sink. The cut contains all the edges that have the one end vertex in X and the other end vertex in V-X. We denote the cut by C(X, V-X).
Illustrate an cut
It is called a cut because if the edges of the cut are removed from the edges of the network then there is no path from the source to the sink.
The capacity of the cut, c(X, V-X), is defined by the sum of the capacities of the edges in the cut.
c = ∑iεX, jεV-X uij
Note that edges from the sink to source across the edge do not contribute to the capacity of the edge.
Illustrate the capacity of cuts
The number of different cuts is nonempty and finite. Why? Therefore, there exist a minimum cut.
The value of a maximum flow in a network is equal to the capacity of its minimum cut.
Proof
Let x be a feasible flow with value v
Let C(X, V-X) be a cut with capacity c.
Consider the flow across the cut, meaning the sum of the flows from X to V-X minus from V-X to X.
It should be obvious that the flow across the cut is equal to the total value of the flow.
From the flow conservation (see Problem 6(b)) the flow across the cut is equal to v.
v = flow from source to sink across cut - flow from sink to source across cut
(*) v = ∑iεX, jεV-X xij - ∑jεV-X, iεX xji is the definition of the flow across the cut
The second sum is nonnegative and the flow xij on any edge cannot exceed the capacity, uij
v ≤ ∑iεX, jεV-X xij ≤ ∑iεX, jεV-X uij = c
in other words
v ≤ c
Therefore the total flow of any feasible flow cannot exceed the capacity of any cut.
We use the above to prove the assertions below.
Let v* be the value of a final flow x* obtained from the augmenting path method. Also, suppose that we can find a cut with capacity v*.
Then (using the v ≤
c)
(i) v* is maximal of all feasible flow
(ii) the cut capacity, v*, has the minimal capacity among all cuts
(iii) the maximum-flow value is equal to the minimal cut capacity.
To finish the Max-flow Min-cut theorem, we only need to find this cut.
Construct X*, made of all the vertices reached from the source in the undirected graph with forward edges that have positive unused capacity with respect to x* and backward edges with positive flow.
X* contains the source but not the sink. If it did contain the sink, this would imply an augmented path exist, which cannot exist because x* is solution from the augmented path method.
Consider the edges (i,j) in C(X*, V-X*).
If the edge (i, j) is a forward edge across the cut, meaning i ε X* and j ε V-X* then it has zero unused capacity, meaning the flow is at the capacity,
xij = uij.
If the edge (i, j) is a backward edge across the cut, meaning j ε X* and i ε V-X*, then it has zero flow on it,
xji = 0.
The flow across the cut is (meaning (*)):
v* = ∑iεX, jεV-X x*ij - ∑jεV-X, iεX x*ji = ∑iεX, jεV-X x*ij - 0 = c(X*, V-X*)
So this cut has capacity equal to the flow
This proves the theorem.
The augmented path method also solve for the minimal cut.
The minimal cut is formed of the edges from labeled to unlabeled vertices on
the last iteration. All these edges are full, have zero remaining capacity.