Module No.

4 Iterative Improvement 5 Hours

The Simplex Method-The Maximum-Flow Problem – Maximum Matching in Bipartite Graphs-
The Stable Marriage Problem.

Iterative Improvement
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.

 The Simplex Method

The classic method for solving LP problems;

one of the most important algorithms ever invented.
 Invented by George Dantzig in 1947.
 Based on the iterative improvement idea.
 Generates a sequence of adjacent points of the problem’s feasible region with
improving values of the objective function until no further improvement is possible.

Linear Programming

 Linear programming problem (LPP) is to optimize a linear function of several

variables subject to linear constraints:

maximize (or minimize) c1 x1 + ...+ cn xn

subject to ai1x1+ ...+ ain xn ≤ (or ≥ or =) bi , i = 1,...,m x1 ≥ 0, ... , xn ≥ 0

The function z = c1 x1 + ...+ cn xn is called the objective function;

constraints x1 ≥ 0, ... , xn ≥ 0 are called nonnegativity constraint

DAA PROF. G. SRINIVASA RAO

DAA PROF. G. SRINIVASA RAO
DAA PROF. G. SRINIVASA RAO
DAA PROF. G. SRINIVASA RAO
DAA PROF. G. SRINIVASA RAO
DAA PROF. G. SRINIVASA RAO
  The Maximum Flow Problem

 The max flow problem is a classic optimization problem in graph theory that
involves finding the maximum amount of flow that can be sent through a network
of pipes, channels, or other pathways, subject to capacity constraints.
 The problem can be used to model a wide variety of real-world situations, such as
transportation systems, communication networks, and resource allocation.
 In the max flow problem, we have a directed graph with a source node s and a sink
node t, and each edge has a capacity that represents the maximum amount of flow
that can be sent through it. The goal is to find the maximum amount of flow that
can be sent from s to t, while respecting the capacity constraints on the edges.
 One common approach to solving the max flow problem is the Ford-Fulkerson
algorithm, which is based on the idea of augmenting paths. The algorithm starts
with an initial flow of zero, and iteratively finds a path from s to t that has available

DAA PROF. G. SRINIVASA RAO

 capacity, and then increases the flow along that path by the maximum amount
possible. This process continues until no more augmenting paths can be found.

Advantages:
1. The max flow problem is a flexible and powerful modeling tool that can be used to
represent a wide variety of real-world situations.
2. The Ford-Fulkerson and Edmonds-Karp algorithms are both guaranteed to find the
maximum flow in a graph, and can be implemented efficiently for most practical
cases.
3. The max flow problem has many interesting theoretical properties and connections
to other areas of mathematics, such as linear programming and combinatorial
optimization.

Disadvantages:
1. In some cases, the max flow problem can be difficult to solve efficiently, especially
if the graph is very large or has complex capacity constraints.
2. The max flow problem may not always provide a unique or globally optimal solution,
depending on the specific problem instance and algorithm used.

Maximum flow problems involve finding a feasible flow through a single-source, single-
sink flow network that is maximum. Let’s take an image to explain how the above
definition wants to say.

DAA PROF. G. SRINIVASA RAO

DAA PROF. G. SRINIVASA RAO
DAA PROF. G. SRINIVASA RAO
  Ford-Fulkerson Algorithm for Maximum Flow Problem

 The Ford-Fulkerson algorithm is a widely used algorithm to solve the maximum

flow problem in a flow network. The maximum flow problem involves determining
the maximum amount of flow that can be sent from a source vertex to a sink vertex
in a directed weighted graph, subject to capacity constraints on the edges.
 The algorithm works by iteratively finding an augmenting path, which is a path from
the source to the sink in the residual graph, i.e., the graph obtained by subtracting
the current flow from the capacity of each edge. The algorithm then increases the
flow along this path by the maximum possible amount, which is the minimum
capacity of the edges along the path.

Problem:
Given a graph which represents a flow network where every edge has a capacity. Also,
given two vertices source ‘s’ and sink ‘t’ in the graph, find the maximum possible flow from
s to t with the following constraints:

 Flow on an edge doesn’t exceed the given capacity of the edge.

 Incoming flow is equal to outgoing flow for every vertex except s and t.

The maximum possible flow in the above graph is 23.

Ford-Fulkerson Algorithm
The following is simple idea of Ford-Fulkerson algorithm:
1. Start with initial flow as 0.
2. While there exists an augmenting path from the source to the sink:
 Find an augmenting path using any path-finding algorithm, such as breadth-
first search or depth-first search.
 Determine the amount of flow that can be sent along the augmenting path,
which is the minimum residual capacity along the edges of the path.
 Increase the flow along the augmenting path by the determined amount.
3. Return the maximum flow.

DAA PROF. G. SRINIVASA RAO

Time Complexity: Time complexity of the above algorithm is O(max_flow * E). We run a
loop while there is an augmenting path. In worst case, we may add 1 unit flow in every
iteration. Therefore the time complexity becomes O(max_flow * E).

 Maximum Matching in Bipartite Graphs

Maximum Bipartite Matching

A Bipartite Graph is a graph whose vertices can be divided into two independent sets L
and R such that every edge (u, v) either connect a vertex from L to R or a vertex from R
to L. In other words, for every edge (u, v) either u ∈ L and v ∈ L. We can also say that no
edge exists that connect vertices of the same set.

Matching is a Bipartite Graph is a set of edges chosen in such a way that no two edges
share an endpoint. Given an undirected Graph G = (V, E), a Matching is a subset of edge
M ⊆ E such that for all vertices v ∈ V, at most one edge of M is incident on v.
A Maximum matching is a matching of maximum cardinality, that is, a matching M such
that for any matching M', we have|M|>|M' |.

Finding a maximum bipartite matching

We can use the Ford-Fulkerson method to find a maximum matching in an undirected
bipartite graph G= (V, E) in time polynomial in |V| and |E|. The trick is to construct a flow
network G= (V',E') for the bipartite graph G as follows. We let the source s and sink t be
new vertices not in V, and we let V'=V ∪{s,t}.If the vertex partition of G is V = L∪R, the
directed edges of G' are the edges of E, directed from L to R, along with |V| new directed
edges:

DAA PROF. G. SRINIVASA RAO

DAA PROF. G. SRINIVASA RAO
DAA PROF. G. SRINIVASA RAO
  The Stable Marriage Problem

The Stable Marriage Problem states that given N men and N women, where each person
has ranked all members of the opposite sex in order of preference, marry the men and
women together such that there are no two people of opposite sex who would both rather
have each other than their current partners. If there are no such people, all the marriages
are “stable” .

Gale–Shapley algorithm to find a stable matching:

The idea is to iterate through all free men while there is any free man available. Every free
man goes to all women in his preference list according to the order. For every woman he
goes to, he checks if the woman is free, if yes, they both become engaged. If the woman
is not free, then the woman chooses either says no to him or dumps her current
engagement according to her preference list. So an engagement done once can be broken
if a woman gets better option. Time Complexity of Gale-Shapley Algorithm is O(n2).

Initialize all men and women to free

while there exist a free man m who still has a woman w to propose to
{
w = m's highest ranked such woman to whom he has not yet proposed
if w is free
(m, w) become engaged
else some pair (m', w) already exists
if w prefers m to m'
(m, w) become engaged
m' becomes free
else
(m', w) remain engaged
}

Time Complexity : O(N2) , where n is number of men/women.

Auxiliary Space : O(N2)

DAA PROF. G. SRINIVASA RAO

DAA PROF. G. SRINIVASA RAO
DAA PROF. G. SRINIVASA RAO
DAA PROF. G. SRINIVASA RAO