assignment problem max flow

• Algorithm Developers
• Python Developers
• Machine Learning Engineers
• Deep Learning Experts
• SQL Developers
• Pandas Developers
• Java Developers
• PostgreSQL Developers

Maximum Flow and the Linear Assignment Problem

The Hungarian graph algorithm solves the linear assignment problem in polynomial time. By modeling resources (e.g., contractors and available contracts) as a graph, the Hungarian algorithm can be used to efficiently determine an optimum way of allocating resources.

By Dmitri Ivanovich Arkhipov

Dmitri has a PhD in computer science from UC Irvine and works primarily in UNIX/Linux ecosystems. He specializes in Python and Java.

PREVIOUSLY AT

Here’s a problem: Your business assigns contractors to fulfill contracts. You look through your rosters and decide which contractors are available for a one month engagement and you look through your available contracts to see which of them are for one month long tasks. Given that you know how effectively each contractor can fulfill each contract, how do you assign contractors to maximize the overall effectiveness for that month?

This is an example of the assignment problem, and the problem can be solved with the classical Hungarian algorithm .

The Hungarian algorithm (also known as the Kuhn-Munkres algorithm) is a polynomial time algorithm that maximizes the weight matching in a weighted bipartite graph. Here, the contractors and the contracts can be modeled as a bipartite graph, with their effectiveness as the weights of the edges between the contractor and the contract nodes.

In this article, you will learn about an implementation of the Hungarian algorithm that uses the Edmonds-Karp algorithm to solve the linear assignment problem. You will also learn how the Edmonds-Karp algorithm is a slight modification of the Ford-Fulkerson method and how this modification is important.

The Maximum Flow Problem

The maximum flow problem itself can be described informally as the problem of moving some fluid or gas through a network of pipes from a single source to a single terminal. This is done with an assumption that the pressure in the network is sufficient to ensure that the fluid or gas cannot linger in any length of pipe or pipe fitting (those places where different lengths of pipe meet).

By making certain changes to the graph, the assignment problem can be turned into a maximum flow problem.

Preliminaries

The ideas needed to solve these problems arise in many mathematical and engineering disciplines, often similar concepts are known by different names and expressed in different ways (e.g., adjacency matrices and adjacency lists). Since these ideas are quite esoteric, choices are made regarding how generally these concepts will be defined for any given setting.

This article will not assume any prior knowledge beyond a little introductory set theory.

The implementations in this post represent the problems as directed graphs (digraph).

A digraph has two attributes , setOfNodes and setOfArcs . Both of these attributes are sets (unordered collections). In the code blocks on this post, I’m actually using Python’s frozenset , but that detail isn’t particularly important.

(Note: This, and all other code in this article, are written in Python 3.6.)

A node n is composed of two attributes:

n.uid : A unique identifier .

This means that for any two nodes x and y ,

• n.datum : This represents any data object.

An arc a is composed of three attributes:

a.fromNode : This is a node , as defined above.

a.toNode : This is a node , as defined above.

a.datum : This represents any data object.

The set of arcs in the digraph represents a binary relation on the nodes in the digraph . The existence of arc a implies that a relationship exists between a.fromNode and a.toNode .

In a directed graph (as opposed to an undirected graph), the existence of a relationship between a.fromNode and a.toNode does not imply that a similar relationship between a.toNode and a.fromNode exists.

This is because in an undirected graph, the relationship being expressed is not necessarily symmetric.

Nodes and arcs can be used to define a digraph , but for convenience, in the algorithms below, a digraph will be represented using as a dictionary .

Here’s a method that can convert the graph representation above into a dictionary representation similar to this one :

And here’s another one that converts it into a dictionary of dictionaries, another operation that will be useful:

When the article talks about a digraph as represented by a dictionary, it will mention G_as_dict to refer to it.

Sometimes it’s helpful to fetch a node from a digraph G by it up through its uid (unique identifier):

In defining graphs, people sometimes use the terms node and vertex to refer to the same concept; the same is true of the terms arc and edge.

Two popular graph representations in Python are this one which uses dictionaries and another which uses objects to represent graphs. The representation in this post is somewhere in between these two commonly used representations.

This is my digraph representation. There are many like it, but this one is mine.

Walks and Paths

Let S_Arcs be a finite sequence (ordered collection) of arcs in a digraph G such that if a is any arc in S_Arcs except for the last, and b follows a in the sequence, then there must be a node n = a.fromNode in G.setOfNodes such that a.toNode = b.fromNode .

Starting from the first arc in S_Arcs , and continuing until the last arc in S_Arcs , collect (in the order encountered) all nodes n as defined above between each two consecutive arcs in S_Arcs . Label the ordered collection of nodes collected during this operation S_{Nodes} .

If any node appears more than once in the sequence S_Nodes then call S_Arcs a Walk on digraph G .

Otherwise, call S_Arcs a path from list(S_Nodes)[0] to list(S_Nodes)[-1] on digraph G .

Source Node

Call node s a source node in digraph G if s is in G.setOfNodes and G.setOfArcs contains no arc a such that a.toNode = s .

Terminal Node

Call node t a terminal node in digraph G if t is in G.setOfNodes and G.setOfArcs contains no arc a such that a.fromNode = t .

Cuts and s-t Cuts

A cut cut of a connected digraph G is a subset of arcs from G.setOfArcs which partitions the set of nodes G.setOfNodes in G . G is connected if every node n in G.setOfNodes and has at least one arc a in G.setOfArcs such that either n = a.fromNode or n = a.toNode , but a.fromNode != a.toNode .

The definition above refers to a subset of arcs , but it can also define a partition of the nodes of G.setOfNodes .

For the functions predecessors_of and successors_of , n is a node in set G.setOfNodes of digraph G , and cut is a cut of G :

Let cut be a cut of digraph G .

cut is a cut of digraph G if: (get_first_part(cut, G).union(get_second_part(cut, G)) == G.setOfNodes) and (len(get_first_part(cut, G).intersect(get_second_part(cut, G))) == 0) cut is called an x-y cut if (x in get_first_part(cut, G)) and (y in get_second_part(cut, G) ) and (x != y) . When the node x in a x-y cut cut is a source node and node y in the x-y cut is a terminal node , then this cut is called a s-t cut .

Flow Networks

You can use a digraph G to represent a flow network.

Assign each node n , where n is in G.setOfNodes an n.datum that is a FlowNodeDatum :

Assign each arc a , where a is in G.setOfArcs and a.datum that is a FlowArcDatum .

flowNodeDatum.flowIn and flowNodeDatum.flowOut are positive real numbers .

flowArcDatum.capacity and flowArcDatum.flow are also positive real numbers.

For every node node n in G.setOfNodes :

Digraph G now represents a flow network .

The flow of G refers to the a.flow for all arcs a in G .

Feasible Flows

Let digraph G represent a flow network .

The flow network represented by G has feasible flows if:

For every node n in G.setOfNodes except for source nodes and terminal nodes : n.datum.flowIn = n.datum.flowOut .

For every arc a in G.setOfNodes : a.datum.capacity <= a.datum.flow .

Condition 1 is called a conservation constraint .

Condition 2 is called a capacity constraint .

Cut Capacity

The cut capacity of an s-t cut stCut with source node s and terminal node t of a flow network represented by a digraph G is:

Minimum Capacity Cut

Let stCut = stCut(s,t,cut) be an s-t cut of a flow network represented by a digraph G .

stCut is the minimum capacity cut of the flow network represented by G if there is no other s-t cut stCutCompetitor in this flow network such that:

Stripping the Flows Away

I would like to refer to the digraph that would be the result of taking a digraph G and stripping away all the flow data from all the nodes in G.setOfNodes and also all the arcs in G.setOfArcs .

Maximum Flow Problem

A flow network represented as a digraph G , a source node s in G.setOfNodes and a terminal node t in G.setOfNodes , G can represent a maximum flow problem if:

Label this representation:

Where sourceNodeUid = s.uid , terminalNodeUid = t.uid , and maxFlowProblemStateUid is an identifier for the problem instance.

Maximum Flow Solution

Let maxFlowProblem represent a maximum flow problem . The solution to maxFlowProblem can be represented by a flow network represented as a digraph H .

Digraph H is a feasible solution to the maximum flow problem on input python maxFlowProblem if:

strip_flows(maxFlowProblem.G) == strip_flows(H) .

H is a flow network and has feasible flows .

If in addition to 1 and 2:

• There can be no other flow network represented by digraph K such that strip_flows(G) == strip_flows(K) and find_node_by_uid(t.uid,G).flowIn < find_node_by_uid(t.uid,K).flowIn .

Then H is also an optimal solution to maxFlowProblem .

In other words a feasible maximum flow solution can be represented by a digraph , which:

Is identical to digraph G of the corresponding maximum flow problem with the exception that the n.datum.flowIn , n.datum.flowOut and the a.datum.flow of any of the nodes and arcs may be different.

Represents a flow network that has feasible flows .

And, it can represent an optimal maximum flow solution if additionally:

• The flowIn for the node corresponding to the terminal node in the maximum flow problem is as large as possible (when conditions 1 and 2 are still satisfied).

If digraph H represents a feasible maximum flow solution : find_node_by_uid(s.uid,H).flowOut = find_node_by_uid(t.uid,H).flowIn this follows from the max flow, min cut theorem (discussed below). Informally, since H is assumed to have feasible flows this means that flow can neither be ‘created’ (except at source node s ) nor ‘destroyed’ (except at terminal node t ) while crossing any (other) node ( conservation constraints ).

Since a maximum flow problem contains only a single source node s and a single terminal node t , all flow ‘created’ at s must be ‘destroyed’ at t or the flow network does not have feasible flows (the conservation constraint would have been violated).

Let digraph H represent a feasible maximum flow solution ; the value above is called the s-t Flow Value of H .

This means that mfps is a successor state of maxFlowProblem , which just means that mfps is exacly like maxFlowProblem with the exception that the values of a.flow for arcs a in maxFlowProblem.setOfArcs may be different than a.flow for arcs a in mfps.setOfArcs .

Here’s a visualization of a mfps along with its associated maxFlowProb . Each arc a in the image has a label, these labels are a.datum.flowFrom / a.datum.flowTo , each node n in the image has a label, and these labels are n.uid {n.datum.flowIn / a.datum.flowOut} .

s-t Cut Flow

Let mfps represent a MaxFlowProblemState and let stCut represent a cut of mfps.G . The cut flow of stCut is defined:

s-t cut flow is the sum of flows from the partition containing the source node to the partition containing the terminal node minus the sum of flows from the partition containing the terminal node to the partition containing the source node .

Max Flow, Min Cut

Let maxFlowProblem represent a maximum flow problem and let the solution to maxFlowProblem be represented by a flow network represented as digraph H .

Let minStCut be the minimum capacity cut of the flow network represented by maxFlowProblem.G .

Because in the maximum flow problem flow originates in only a single source node and terminates at a single terminal node and, because of the capacity constraints and the conservation constraints , we know that the all of the flow entering maxFlowProblem.terminalNodeUid must cross any s-t cut , in particular it must cross minStCut . This means:

Solving the Maximum Flow Problem

The basic idea for solving a maximum flow problem maxFlowProblem is to start with a maximum flow solution represented by digraph H . Such a starting point can be H = strip_flows(maxFlowProblem.G) . The task is then to use H and by some greedy modification of the a.datum.flow values of some arcs a in H.setOfArcs to produce another maximum flow solution represented by digraph K such that K cannot still represent a flow network with feasible flows and get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) . As long as this process continues, the quality ( get_flow_value(K, maxFlowProblem) ) of the most recently encountered maximum flow solution ( K ) is better than any other maximum flow solution that has been found. If the process reaches a point that it knows that no other improvement is possible, the process can terminate and it will return the optimal maximum flow solution .

The description above is general and skips many proofs such as whether such a process is possible or how long it may take, I’ll give a few more details and the algorithm.

The Max Flow, Min Cut Theorem

From the book Flows in Networks by Ford and Fulkerson , the statement of the max flow, min cut theorem (Theorem 5.1) is:

For any network, the maximal flow value from s to t is equal to the minimum cut capacity of all cuts separating s and t .

Using the definitions in this post, that translates to:

The solution to a maxFlowProblem represented by a flow network represented as digraph H is optimal if:

I like this proof of the theorem and Wikipedia has another one .

The max flow, min cut theorem is used to prove the correctness and completeness of the Ford-Fulkerson method .

I’ll also give a proof of the theorem in the section after augmenting paths .

The Ford-Fulkerson Method and the Edmonds-Karp Algorithm

CLRS defines the Ford-Fulkerson method like so (section 26.2):

Residual Graph

The Residual Graph of a flow network represented as the digraph G can be represented as a digraph G_f :

agg_n_to_u_cap(n,u,G_as_dict) returns the sum of a.datum.capacity for all arcs in the subset of G.setOfArcs where arc a is in the subset if a.fromNode = n and a.toNode = u .

agg_n_to_u_cap(n,u,G_as_dict) returns the sum of a.datum.flow for all arcs in the subset of G.setOfArcs where arc a is in the subset if a.fromNode = n and a.toNode = u .

Briefly, the residual graph G_f represents certain actions which can be performed on the digraph G .

Each pair of nodes n,u in G.setOfNodes of the flow network represented by digraph G can generate 0, 1, or 2 arcs in the residual graph G_f of G .

The pair n,u does not generate any arcs in G_f if there is no arc a in G.setOfArcs such that a.fromNode = n and a.toNode = u .

The pair n,u generates the arc a in G_f.setOfArcs where a represents an arc labeled a push flow arc from n to u a = Arc(n,u,datum=ResidualNode(n_to_u_cap_sum - n_to_u_flow_sum)) if n_to_u_cap_sum > n_to_u_flow_sum .

The pair n,u generates the arc a in G_f.setOfArcs where a represents an arc labeled a pull flow arc from n to u a = Arc(n,u,datum=ResidualNode(n_to_u_cap_sum - n_to_u_flow_sum)) if n_to_u_flow_sum > 0.0 .

Each push flow arc in G_f.setOfArcs represents the action of adding a total of x <= n_to_u_cap_sum - n_to_u_flow_sum flow to arcs in the subset of G.setOfArcs where arc a is in the subset if a.fromNode = n and a.toNode = u .

Each pull flow arc in G_f.setOfArcs represents the action of subtracting a total of x <= n_to_u_flow_sum flow to arcs in the subset of G.setOfArcs where arc a is in the subset if a.fromNode = n and a.toNode = u .

Performing an individual push or pull action from G_f on the applicable arcs in G might generate a flow network without feasible flows because the capacity constraints or the conservation constraints might be violated in the generated flow network .

Here’s a visualization of the residual graph of the previous example visualization of a maximum flow solution , in the visualization each arc a represents a.residualCapacity .

Augmenting Path

Let maxFlowProblem be a max flow problem , and let G_f = get_residual_graph_of(G) be the residual graph of maxFlowProblem.G .

An augmenting path augmentingPath for maxFlowProblem is any path from find_node_by_uid(maxFlowProblem.sourceNode,G_f) to find_node_by_uid(maxFlowProblem.terminalNode,G_f) .

It turns out that an augmenting path augmentingPath can be applied to a max flow solution represented by digraph H generating another max flow solution represented by digraph K where get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) if H is not optimal .

Here’s how:

In the above, TOL is some tolerance value for rounding the flow values in the network. This is to avoid cascading imprecision of floating point calculations . So, for example, I used TOL = 10 to mean round to 10 significant digits .

Let K = augment(augmentingPath, H) , then K represents a feasible max flow solution for maxFlowProblem . For the statement to be true, the flow network represented by K must have feasible flows (not violate the capacity constraint or the conservation constraint .

Here’s why: In the method above, each node added to the new flow network represented by digraph K is either an exact copy of a node from digraph H or a node n which has had the same number added to its n.datum.flowIn as its n.datum.flowOut . This means that the conservation constraint is satisfied in K as long as it was satisfied in H . The conservation constraint is satisfied because we explicitly check that any new arc a in the network has a.datum.flow <= a.datum.capacity ; thus, as long as the arcs from the set H.setOfArcs which were copied unmodified into K.setOfArcs do not violate the capacity constraint , then K does not violate the capacity constraint .

It’s also true that get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) if H is not optimal .

Here’s why: For an augmenting path augmentingPath to exist in the digraph representation of the residual graph G_f of a max flow problem maxFlowProblem then the last arc a on augmentingPath must be a ‘push’ arc and it must have a.toNode == maxFlowProblem.terminalNode . An augmenting path is defined as one which terminates at the terminal node of the max flow problem for which it is an augmenting path . From the definition of the residual graph , it is clear that the last arc in an augmenting path on that residual graph must be a ‘push’ arc because any ‘pull’ arc b in the augmenting path will have b.toNode == maxFlowProblem.terminalNode and b.fromNode != maxFlowProblem.terminalNode from the definition of path . Additionally, from the definition of path , it is clear that the terminal node is only modified once by the augment method. Thus augment modifies maxFlowProblem.terminalNode.flowIn exactly once and it increases the value of maxFlowProblem.terminalNode.flowIn because the last arc in the augmentingPath must be the arc which causes the modification in maxFlowProblem.terminalNode.flowIn during augment . From the definition of augment as it applies to ‘push’ arcs , the maxFlowProblem.terminalNode.flowIn can only be increased, not decreased.

Some Proofs from Sedgewick and Wayne

The book Algorithms, fourth edition by Robert Sedgewich and Kevin Wayne has some wonderful and short proofs (pages 892-894) that will be useful. I’ll recreate them here, though I’ll use language fitting in with previous definitions. My labels for the proofs are the same as in the Sedgewick book.

Proposition E: For any digraph H representing a feasible maximum flow solution to a maximum flow problem maxFlowProblem , for any stCut get_stcut_flow(stCut,H,maxFlowProblem) = get_flow_value(H, maxFlowProblem) .

Proof: Let stCut=stCut(maxFlowProblem.sourceNode,maxFlowProblem.terminalNode,set([a for a in H.setOfArcs if a.toNode == maxFlowProblem.terminalNode])) . Proposition E holds for stCut directly from the definition of s-t flow value . Suppose that there we wish to move some node n from the s-partition ( get_first_part(stCut.cut, G) ) and into the t-partition (get_second_part(stCut.cut, G)) , to do so we need to change stCut.cut , which could change stcut_flow = get_stcut_flow(stCut,H,maxFlowProblem) and invalidate proposition E . However, let’s see how the value of stcut_flow will change as we make this change. node n is at equilibrium meaning that the sum of flow into node n is equal to the sum of flow out of it (this is necessary for H to represent a feasible solution ). Notice that all flow which is part of the stcut_flow entering node n enters it from the s-partition (flow entering node n from the t-partition either directly or indirectly would not have been counted in the stcut_flow value because it is heading the wrong direction based on the definition). Additionally, all flow exiting n will eventually (directly or indirectly) flow into the terminal node (proved earlier). When we move node n into the t-partition, all the flow entering n from the s-partition must be added to the new stcut_flow value; however, all flow exiting n must the be subtracted from the new stcut_flow value; the part of the flow heading directly into the t-partition is subtracted because this flow is now internal to the new t-partition and is not counted as stcut_flow . The part of the flow from n heading into nodes in the s-partition must also be subtracted from stcut_flow : After n is moved into the t-partition, these flows will be directed from the t-partition and into the s-partition and so must not be accounted for in the stcut_flow , since these flows are removed the inflow into the s-partition and must be reduced by the sum of these flows, and the outflow from the s-partition into the t-partition (where all flows from s-t must end up) must be reduced by the same amount. As node n was at equilibrium prior to the process, the update will have added the same value to the new stcut_flow value as it subtracted thus leaving proposition E true after the update. The validity of proposition E then follows from induction on the size of the t-partition.

Here are some example flow networks to help visualize the less obvious cases where proposition E holds; in the image, the red areas indicate the s-partition, the blue areas represent the t-partition, and the green arcs indicate an s-t cut . In the second image, flow between node A and node B increases while the flow into terminal node t doesn’t change.:

Corollary: No s-t cut flow value can exceed the capacity of any s-t cut .

Proposition F. (max flow, min cut theorem): Let f be an s-t flow . The following 3 conditions are equivalent:

There exists an s-t cut whose capacity equals the value of the flow f .

f is a max flow .

There is no augmenting path with respect to f .

Condition 1 implies condition 2 by the corollary. Condition 2 implies condition 3 because the existence of an augmenting path implies the existence of a flow with larger values, contradicting the maximality of f . Condition 3 implies condition 1: Let C_s be the set of all nodes that can be reached from s with an augmenting path in the residual graph . Let C_t be the remaining arcs , then t must be in C_t (by our assumption). The arcs crossing from C_s to C_t then form an s-t cut which contains only arcs a where either a.datum.capacity = a.datum.flow or a.datum.flow = 0.0 . If this were otherwise then the nodes connected by an arc with remaining residual capacity to C_s would be in the set C_s since there would then be an augmenting path from s to such a node . The flow across the s-t cut is equal to the s-t cut’s capacity (since arcs from C_s to C_t have flow equal to capacity) and also to the value of the s-t flow (by proposition E ).

This statement of the max flow, min cut theorem implies the earlier statement from Flows in Networks .

Corollary (integrality property): When capacities are integers, there exists an integer-valued max flow, and the Ford-Fulkerson algorithm finds it.

Proof: Each augmenting path increases the flow by a positive integer, the minimum of the unused capacities in the ‘push’ arcs and the flows in the ‘pull’ arcs , all of which are always positive integers.

This justifies the Ford-Fulkerson method description from CLRS . The method is to keep finding augmenting paths and applying augment to the latest maxFlowSolution coming up with better solutions, until no more augmenting path meaning that the latest maximum flow solution is optimal .

From Ford-Fulkerson to Edmonds-Karp

The remaining questions regarding solving maximum flow problems are:

How should augmenting paths be constructed?

Will the method terminate if we use real numbers and not integers?

How long will it take to terminate (if it does)?

The Edmonds-Karp algorithm specifies that each augmenting path is constructed by a breadth first search ( BFS ) of the residual graph ; it turns out that this decision of point 1 above will also force the algorithm to terminate (point 2) and allows the asymptotic time and space complexity to be determined.

First, here’s a BFS implementation:

I used a deque from the python collections module .

To answer question 2 above, I’ll paraphrase another proof from Sedgewick and Wayne : Proposition G. The number of augmenting paths needed in the Edmonds-Karp algorithm with N nodes and A arcs is at most NA/2 . Proof: Every augmenting path has a bottleneck arc - an arc that is deleted from the residual graph because it corresponds either to a ‘push’ arc that becomes filled to capacity or a ‘pull’ arc through which the flow becomes 0. Each time an arc becomes a bottleneck arc , the length of any augmenting path through it must increase by a factor of 2. This is because each node in a path may appear only once or not at all (from the definition of path ) since the paths are being explored from shortest path to longest that means that at least one more node must be visited by the next path that goes through the particular bottleneck node that means an additional 2 arcs on the path before we arrive at the node . Since the augmenting path is of length at most N each arc can be on at most N/2 augmenting paths , and the total number of augmenting paths is at most NA/2 .

The Edmonds-Karp algorithm executes in O(NA^2) . If at most NA/2 paths will be explored during the algorithm and exploring each path with BFS is N+A then the most significant term of the product and hence the asymptotic complexity is O(NA^2) .

Let mfp be a maxFlowProblemState .

The version above is inefficient and has worse complexity than O(NA^2) since it constructs a new maximum flow solution and new a residual graph each time (rather than modifying existing digraphs as the algorithm advances). To get to a true O(NA^2) solution the algorithm must maintain both the digraph representing the maximum flow problem state and its associated residual graph . So the algorithm must avoid iterating over arcs and nodes unnecessarily and update their values and associated values in the residual graph only as necessary.

To write a faster Edmonds Karp algorithm, I rewrote several pieces of code from the above. I hope that going through the code which generated a new digraph was helpful in understanding what’s going on. In the fast algorithm, I use some new tricks and Python data structures that I don’t want to go over in detail. I will say that a.fromNode and a.toNode are now treated as strings and uids to nodes . For this code, let mfps be a maxFlowProblemState

Here’s a visualization of how this algorithm solves the example flow network from above. The visualization shows the steps as they are reflected in the digraph G representing the most up-to-date flow network and as they are reflected in the residual graph of that flow network. Augmenting paths in the residual graph are shown as red paths, and the digraph representing the problem the set of nodes and arcs affected by a given augmenting path is highlighted in green. In each case, I’ll highlight the parts of the graph that will be changed (in red or green) and then show the graph after the changes (just in black).

Here’s another visualization of how this algorithm solving a different example flow network . Notice that this one uses real numbers and contains multiple arcs with the same fromNode and toNode values.

**Also notice that because Arcs with a ‘pull’ ResidualDatum may be part of the Augmenting Path, the nodes affected in the DiGraph of the Flown Network _may not be on a path in G! .

Bipartite Graphs

Suppose we have a digraph G , G is bipartite if it’s possible to partition the nodes in G.setOfNodes into two sets ( part_1 and part_2 ) such that for any arc a in G.setOfArcs it cannot be true that a.fromNode in part_1 and a.toNode in part_1 . It also cannot be true that a.fromNode in part_2 and a.toNode in part_2 .

In other words G is bipartite if it can be partitioned into two sets of nodes such that every arc must connect a node in one set to a node in the other set.

Testing Bipartite

Suppose we have a digraph G , we want to test if it is bipartite . We can do this in O(|G.setOfNodes|+|G.setOfArcs|) by greedy coloring the graph into two colors.

First, we need to generate a new digraph H . This graph will have will have the same set of nodes as G , but it will have more arcs than G . Every arc a in G will create 2 arcs in H ; the first arc will be identical to a , and the second arc reverses the director of a ( b = Arc(a.toNode,a.fromNode,a.datum) ).

Matchings and Maximum Matchings

Suppose we have a digraph G and matching is a subset of arcs from G.setOfArcs . matching is a matching if for any two arcs a and b in matching : len(frozenset( {a.fromNode} ).union( {a.toNode} ).union( {b.fromNode} ).union( {b.toNode} )) == 4 . In other words, no two arcs in a matching share a node .

Matching matching , is a maximum matching if there is no other matching alt_matching in G such that len(matching) < len(alt_matching) . In other words, matching is a maximum matching if it is the largest set of arcs from G.setOfArcs that still satisfies the definition of matching (the addition of any arc not already in the matching will break the matching definition).

A maximum matching matching is a perfect matching if every for node n in G.setOfArcs there exists an arc a in matching where a.fromNode == n or a.toNode == n .

Maximum Bipartite Matching

A maximum bipartite matching is a maximum matching on a digraph G which is bipartite .

Given that G is bipartite , the problem of finding a maximum bipartite matching can be transformed into a maximum flow problem solvable with the Edmonds-Karp algorithm and then the maximum bipartite matching can be recovered from the solution to the maximum flow problem .

Let bipartition be a bipartition of G .

To do this, I need to generate a new digraph ( H ) with some new nodes ( H.setOfNodes ) and some new arcs ( H.setOfArcs ). H.setOfNodes contains all the nodes in G.setOfNodes and two more nodess , s (a source node ) and t (a terminal node ).

H.setOfArcs will contain one arc for each G.setOfArcs . If an arc a is in G.setOfArcs and a.fromNode is in bipartition.firstPart and a.toNode is in bipartition.secondPart then include a in H (adding a FlowArcDatum(1,0) ).

If a.fromNode is in bipartition.secondPart and a.toNode is in bipartition.firstPart , then include Arc(a.toNode,a.fromNode,FlowArcDatum(1,0)) in H.setOfArcs .

The definition of a bipartite graph ensures that no arc connects any nodes where both nodes are in the same partition. H.setOfArcs also contains an arc from node s to each node in bipartition.firstPart . Finally, H.setOfArcs contains an arc each node in bipartition.secondPart to node t . a.datum.capacity = 1 for all a in H.setOfArcs .

First partition the nodes in G.setOfNodes the two disjoint sets ( part1 and part2 ) such that no arc in G.setOfArcs is directed from one set to the same set (this partition is possible because G is bipartite ). Next, add all arcs in G.setOfArcs which are directed from part1 to part2 into H.setOfArcs . Then create a single source node s and a single terminal node t and create some more arcs

Then, construct a maxFlowProblemState .

Minimal Node Cover

A node cover in a digraph G is a set of nodes ( cover ) from G.setOfNodes such that for any arc a of G.setOfArcs this must be true: (a.fromNode in cover) or (a.toNode in cover) .

A minimal node cover is the smallest possible set of nodes in the graph that is still a node cover . König’s theorem states that in a bipartite graph, the size of the maximum matching on that graph is equal to the size of the minimal node cover , and it suggests how the node cover can recovered from a maximum matching :

Suppose we have the bipartition bipartition and the maximum matching matching . Define a new digraph H , H.setOfNodes=G.setOfNodes , the arcs in H.setOfArcs are the union of two sets.

The first set is arcs a in matching , with the change that if a.fromNode in bipartition.firstPart and a.toNode in bipartition.secondPart then a.fromNode and a.toNode are swapped in the created arc give such arcs a a.datum.inMatching=True attribute to indicate that they were derived from arcs in a matching .

The second set is arcs a NOT in matching , with the change that if a.fromNode in bipartition.secondPart and a.toNode in bipartition.firstPart then a.fromNode and a.toNode are swapped in the created arc (give such arcs a a.datum.inMatching=False attribute).

Next, run a depth first search ( DFS ) starting from each node n in bipartition.firstPart which is neither n == a.fromNode nor n == a.toNodes for any arc a in matching . During the DFS, some nodes are visited and some are not (store this information in a n.datum.visited field). The minimum node cover is the union of the nodes {a.fromNode for a in H.setOfArcs if ( (a.datum.inMatching) and (a.fromNode.datum.visited) ) } and the nodes {a.fromNode for a in H.setOfArcs if (a.datum.inMatching) and (not a.toNode.datum.visited)} .

This can be shown to lead from a maximum matching to a minimal node cover by a proof by contradiction , take some arc a that was supposedly not covered and consider all four cases regarding whether a.fromNode and a.toNode belong (whether as toNode or fromNode ) to any arc in matching matching . Each case leads to a contradiction due to the order that DFS visits nodes and the fact that matching is a maximum matching .

Suppose we have a function to execute these steps and return the set of nodes comprising the minimal node cover when given the digraph G , and the maximum matching matching :

The Linear Assignment Problem

The linear assignment problem consists of finding a maximum weight matching in a weighted bipartite graph.

Problems like the one at the very start of this post can be expressed as a linear assignment problem . Given a set of workers, a set of tasks, and a function indicating the profitability of an assignment of one worker to one task, we want to maximize the sum of all assignments that we make; this is a linear assignment problem .

Assume that the number of tasks and workers are equal, though I will show that this assumption is easy to remove. In the implementation, I represent arc weights with an attribute a.datum.weight for an arc a .

Kuhn-Munkres Algorithm

The Kuhn-Munkres Algorithm solves the linear assignment problem . A good implementation can take O(N^{4}) time, (where N is the number of nodes in the digraph representing the problem). An implementation that is easier to explain takes O(N^{5}) (for a version which regenerates DiGraphs ) and O(N^{4}) for (for a version which maintains DiGraphs ). This is similar to the two different implementations of the Edmonds-Karp algorithm.

For this description, I’m only working with complete bipartite graphs (those where half the nodes are in one part of the bipartition and the other half in the second part). In the worker, task motivation this means that there are as many workers as tasks.

This seems like a significant condition (what if these sets are not equal!) but it is easy to fix this issue; I talk about how to do that in the last section.

The version of the algorithm described here uses the useful concept of zero weight arcs . Unfortunately, this concept only makes sense when we are solving a minimization (if rather than maximizing the profits of our worker-task assignments we were instead minimizing the cost of such assignments).

Fortunately, it is easy to turn a maximum linear assignment problem into a minimum linear assignment problem by setting each the arc a weights to M-a.datum.weight where M=max({a.datum.weight for a in G.setOfArcs}) . The solution to the original maximizing problem will be identical to the solution minimizing problem after the arc weights are changed. So for the remainder, assume that we make this change.

The Kuhn-Munkres algorithm solves minimum weight matching in a weighted bipartite graph by a sequence of maximum matchings in unweighted bipartite graphs. If a we find a perfect matching on the digraph representation of the linear assignment problem , and if the weight of every arc in the matching is zero, then we have found the minimum weight matching since this matching suggests that all nodes in the digraph have been matched by an arc with the lowest possible cost (no cost can be lower than 0, based on prior definitions).

No other arcs can be added to the matching (because all nodes are already matched) and no arcs should be removed from the matching because any possible replacement arc will have at least as great a weight value.

If we find a maximum matching of the subgraph of G which contains only zero weight arcs , and it is not a perfect matching , we don’t have a full solution (since the matching is not perfect ). However, we can produce a new digraph H by changing the weights of arcs in G.setOfArcs in a way that new 0-weight arcs appear and the optimal solution of H is the same as the optimal solution of G . Since we guarantee that at least one zero weight arc is produced at each iteration, we guarantee that we will arrive at a perfect matching in no more than |G.setOfNodes|^{2}=N^{2} such iterations.

Suppose that in bipartition bipartition , bipartition.firstPart contains nodes representing workers, and bipartition.secondPart represents nodes representing tasks.

The algorithm starts by generating a new digraph H . H.setOfNodes = G.setOfNodes . Some arcs in H are generated from nodes n in bipartition.firstPart . Each such node n generates an arc b in H.setOfArcs for each arc a in bipartition.G.setOfArcs where a.fromNode = n or a.toNode = n , b=Arc(a.fromNode, a.toNode, a.datum.weight - z) where z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )) .

More arcs in H are generated from nodes n in bipartition.secondPart . Each such node n generates an arc b in H.setOfArcs for each arc a in bipartition.G.setOfArcs where a.fromNode = n or a.toNode = n , b=Arc(a.fromNode, a.toNode, ArcWeightDatum(a.datum.weight - z)) where z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )) .

KMA: Next, form a new digraph K composed of only the zero weight arcs from H , and the nodes incident on those arcs . Form a bipartition on the nodes in K , then use solve_mbm( bipartition ) to get a maximum matching ( matching ) on K . If matching is a perfect matching in H (the arcs in matching are incident on all nodes in H.setOfNodes ) then the matching is an optimal solution to the linear assignment problem .

Otherwise, if matching is not perfect , generate the minimal node cover of K using node_cover = get_min_node_cover(matching, bipartition(K)) . Next, define z=min({a.datum.weight for a in H.setOfArcs if a not in node_cover}) . Define nodes = H.setOfNodes , arcs1 = {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh-z)) for a in H.setOfArcs if ( (a.fromNode not in node_cover) and (a.toNode not in node_cover)} , arcs2 = {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh)) for a in H.setOfArcs if ( (a.fromNode not in node_cover) != (a.toNode not in node_cover)} , arcs3 = {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh+z)) for a in H.setOfArcs if ( (a.fromNode in node_cover) and (a.toNode in node_cover)} . The != symbol in the previous expression acts as an XOR operator. Then arcs = arcs1.union(arcs2.union(arcs3)) . Next, H=DiGraph(nodes,arcs) . Go back to the label KMA . The algorithm continues until a perfect matching is produced. This matching is also the solution to the linear assignment problem .

This implementation is O(N^{5}) because it generates a new maximum matching matching at each iteration; similar to the previous two implementations of Edmonds-Karp this algorithm can be modified so that it keeps track of the matching and adapts it intelligently to each iteration. When this is done, the complexity becomes O(N^{4}) . A more advanced and more recent version of this algorithm (requiring some more advanced data structures) can run in O(N^{3}) . Details of both the simpler implementation above and the more advanced implementation can be found at this post which motivated this blog post.

None of the operations on arc weights modify the final assignment returned by the algorithm. Here’s why: Since our input graphs are always complete bipartite graphs a solution must map each node in one partition to another node in the second partition, via the arc between these two nodes . Notice that the operations performed on the arc weights never changes the order (ordered by weight) of the arcs incident on any particular node .

Thus when the algorithm terminates at a perfect complete bipartite matching each node is assigned a zero weight arc , since the relative order of the arcs from that node hasn’t changed during the algorithm, and since a zero weight arc is the cheapest possible arc and the perfect complete bipartite matching guarantees that one such arc exists for each node . This means that the solution generated is indeed the same as the solution from the original linear assignment problem without any modification of arc weights.

Unbalanced Assignments

It seems like the algorithm is quite limited since as described it operates only on complete bipartite graphs (those where half the nodes are in one part of the bipartition and the other half in the second part). In the worker, task motivation this means that there are as many workers as tasks (seems quite limiting).

However, there is an easy transformation that removes this restriction. Suppose that there are fewer workers than tasks, we add some dummy workers (enough to make the resulting graph a complete bipartite graph ). Each dummy worker has an arc directed from the worker to each of the tasks. Each such arc has weight 0 (placing it in a matching gives no added profit). After this change the graph is a complete bipartite graph which we can solve for. Any task assigned a dummy worker is not initiated.

Suppose that there are more tasks than workers. We add some dummy tasks (enough to make the resulting graph a complete bipartite graph ). Each dummy task has an arc directed from each worker to the dummy task. Each such arc has a weight of 0 (placing it in a matching gives no added profit). After this change the graph is a complete bipartite graph which we can solve for. Any worker assigned to dummy task is not employed during the period.

A Linear Assignment Example

Finally, let’s do an example with the code I’ve been using. I’m going to modify the example problem from here . We have 3 tasks: we need to clean the bathroom , sweep the floor , and wash the windows .

The workers available to use are Alice , Bob , Charlie , and Diane . Each of the workers gives us the wage they require per task. Here are the wages per worker:

If we want to pay the least amount of money, but still get all the tasks done, who should do what task? Start by introducing a dummy task to make the digraph representing the problem bipartite.

Supposing that the problem is encoded in a digraph , then kuhn_munkres( bipartition(G) ) will solve the problem and return the assignment. It’s easy to verify that the optimal (lowest cost) assignment will cost $5.

Here’s a visualization of the solution the code above generates:

That is it. You now know everything you need to know about the linear assignment problem.

You can find all of the code from this article on GitHub .

Further Reading on the Toptal Blog:

• Graph Data Science With Python/NetworkX

Dmitri Ivanovich Arkhipov

Irvine, CA, United States

Member since January 23, 2017

About the author

World-class articles, delivered weekly.

By entering your email, you are agreeing to our privacy policy .

Toptal Developers

• Adobe Commerce (Magento) Developers
• Angular Developers
• AWS Developers
• Azure Developers
• Big Data Architects
• Blockchain Developers
• Business Intelligence Developers
• C Developers
• Computer Vision Developers
• Django Developers
• Docker Developers
• Elixir Developers
• Go Engineers
• GraphQL Developers
• Jenkins Developers
• Kotlin Developers
• Kubernetes Developers
• .NET Developers
• R Developers
• React Native Developers
• Ruby on Rails Developers
• Salesforce Developers
• Tableau Developers
• Unreal Engine Developers
• Xamarin Developers
• View More Freelance Developers

Join the Toptal ® community.

The assignment problem revisited

• Original Paper
• Published: 16 August 2021
• Volume 16 , pages 1531–1548, ( 2022 )

Cite this article

• Carlos A. Alfaro   ORCID: orcid.org/0000-0001-9783-8587 1 ,
• Sergio L. Perez 2 ,
• Carlos E. Valencia 3 &
• Marcos C. Vargas 1  

1072 Accesses

4 Citations

4 Altmetric

Explore all metrics

First, we give a detailed review of two algorithms that solve the minimization case of the assignment problem, the Bertsekas auction algorithm and the Goldberg & Kennedy algorithm. It was previously alluded that both algorithms are equivalent. We give a detailed proof that these algorithms are equivalent. Also, we perform experimental results comparing the performance of three algorithms for the assignment problem: the \(\epsilon \) - scaling auction algorithm , the Hungarian algorithm and the FlowAssign algorithm . The experiment shows that the auction algorithm still performs and scales better in practice than the other algorithms which are harder to implement and have better theoretical time complexity.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Similar content being viewed by others

Some results on an assignment problem variant

Integer Programming

A Full Description of Polytopes Related to the Index of the Lowest Nonzero Row of an Assignment Matrix

Bertsekas, D.P.: The auction algorithm: a distributed relaxation method for the assignment problem. Annal Op. Res. 14 , 105–123 (1988)

Article   MathSciNet   Google Scholar  

Bertsekas, D.P., Castañon, D.A.: Parallel synchronous and asynchronous implementations of the auction algorithm. Parallel Comput. 17 , 707–732 (1991)

Article   Google Scholar  

Bertsekas, D.P.: Linear network optimization: algorithms and codes. MIT Press, Cambridge, MA (1991)

MATH   Google Scholar  

Bertsekas, D.P.: The auction algorithm for shortest paths. SIAM J. Optim. 1 , 425–477 (1991)

Bertsekas, D.P.: Auction algorithms for network flow problems: a tutorial introduction. Comput. Optim. Appl. 1 , 7–66 (1992)

Bertsekas, D.P., Castañon, D.A., Tsaknakis, H.: Reverse auction and the solution of inequality constrained assignment problems. SIAM J. Optim. 3 , 268–299 (1993)

Bertsekas, D.P., Eckstein, J.: Dual coordinate step methods for linear network flow problems. Math. Progr., Ser. B 42 , 203–243 (1988)

Bertsimas, D., Tsitsiklis, J.N.: Introduction to linear optimization. Athena Scientific, Belmont, MA (1997)

Google Scholar  

Burkard, R., Dell’Amico, M., Martello, S.: Assignment Problems. Revised reprint. SIAM, Philadelphia, PA (2011)

Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for network problems. SIAM J. Comput. 18 (5), 1013–1036 (1989)

Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum flow problem. J. Assoc. Comput. Mach. 35 , 921–940 (1988)

Goldberg, A.V., Tarjan, R.E.: Finding minimum-cost circulations by successive approximation. Math. Op. Res. 15 , 430–466 (1990)

Goldberg, A.V., Kennedy, R.: An efficient cost scaling algorithm for the assignment problem. Math. Programm. 71 , 153–177 (1995)

MathSciNet   MATH   Google Scholar  

Goldberg, A.V., Kennedy, R.: Global price updates help. SIAM J. Discr. Math. 10 (4), 551–572 (1997)

Kuhn, H.W.: The Hungarian method for the assignment problem. Naval Res. Logist. Quart. 2 , 83–97 (1955)

Kuhn, H.W.: Variants of the Hungarian method for the assignment problem. Naval Res. Logist. Quart. 2 , 253–258 (1956)

Lawler, E.L.: Combinatorial optimization: networks and matroids, Holt. Rinehart & Winston, New York (1976)

Orlin, J.B., Ahuja, R.K.: New scaling algorithms for the assignment ad minimum mean cycle problems. Math. Programm. 54 , 41–56 (1992)

Ramshaw, L., Tarjan, R.E., Weight-Scaling Algorithm, A., for Min-Cost Imperfect Matchings in Bipartite Graphs, : IEEE 53rd Annual Symposium on Foundations of Computer Science. New Brunswick, NJ 2012 , 581–590 (2012)

Zaki, H.: A comparison of two algorithms for the assignment problem. Comput. Optim. Appl. 4 , 23–45 (1995)

Download references

Acknowledgements

This research was partially supported by SNI and CONACyT.

Author information

Authors and affiliations.

Banco de México, Mexico City, Mexico

Carlos A. Alfaro & Marcos C. Vargas

Mountain View, CA, 94043, USA

Sergio L. Perez

Departamento de Matemáticas, CINVESTAV del IPN, Apartado postal 14-740, 07000, Mexico City, Mexico

Carlos E. Valencia

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Carlos A. Alfaro .

Ethics declarations

Conflict of interest.

There is no conflict of interest.

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The authors were partially supported by SNI and CONACyT.

Rights and permissions

Reprints and permissions

About this article

Alfaro, C.A., Perez, S.L., Valencia, C.E. et al. The assignment problem revisited. Optim Lett 16 , 1531–1548 (2022). https://doi.org/10.1007/s11590-021-01791-4

Download citation

Received : 26 March 2020

Accepted : 03 August 2021

Published : 16 August 2021

Issue Date : June 2022

DOI : https://doi.org/10.1007/s11590-021-01791-4

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Assignment problem
• Bertsekas auction algorithm
• Combinatorial optimization and matching
• Find a journal
• Publish with us
• Track your research

• Google OR-Tools
• Español – América Latina
• Português – Brasil
• Tiếng Việt

Maximum Flows

In the following sections, you get an example of a maximum flow ( max flow ) problem.

A max flow example

The problem is defined by the following graph, which represents a transportation network:

You want to transport material from node 0 (the source ) to node 4 (the sink ). The numbers next to the arcs are their capacities — the capacity of an arc is the maximum amount that can be transported across it in a fixed period of time. The capacities are the constraints for the problem.

A flow is an assignment of a non-negative number to each arc (the flow amount ) that satisfies the following flow conservation rule:

The max flow problem is to find a flow for which the sum of the flow amounts for the entire network is as large as possible.

The following sections present a programs to find the maximum flow from the source (0) to the sink (4).

Import the libraries

The following code imports the required library.

Declare the solver

To solve the problem, you can use the SimpleMaxFlow solver.

Define the data

You define the graph for the problem with three arrays, for the start nodes, end nodes, and capacities of the arcs. The length of each array equals the number of arcs in the graph.

For each i, arc i goes from start_nodes[i] to end_nodes[i] , and its capacity is given by capacities[i] . The next section shows how to create the arcs using this data.

Add the arcs

For each start node and end node, you create an arc from start node to end node with the given capacity, using the method AddArcWithCapacity . The capacities are the constraints for the problem.

Invoke the solver

Now that all the arcs have been defined, all that remains is to invoke the solver and display the results. You invoke the Solve() method, providing the source (0) and sink (4).

Display the results

Now, you can display the flow across each arc.

Here is the output of the program:

The flow amounts across each arc are displayed under Flow .

Complete programs

Putting it all together, here are the complete programs.

Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License , and code samples are licensed under the Apache 2.0 License . For details, see the Google Developers Site Policies . Java is a registered trademark of Oracle and/or its affiliates.

Last updated 2024-08-28 UTC.

Browse Course Material

Course info.

• Prof. Michel Goemans

Departments

• Electrical Engineering and Computer Science
• Mathematics

As Taught In

• Algorithms and Data Structures
• Theory of Computation

Learning Resource Types

Advanced algorithms, network flows.

Lecture notes on network flows, the single source shortest path problem, the maximum flow problem, the minimum cost circulation problem, the maximum flow problem, bipartite matching, a circulation of minimum cost, Klein’s cycle canceling algorithm, the Goldberg-Tarjan algorithm, a faster cycle-canceling algorithm, and a strongly polynomial bound.

You are leaving MIT OpenCourseWare

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Solving assignment problem using Hungarian method vs min cost max flow problem

The traditional solution for the assignment problem is the Hungarian method - it's complexity is O(V^4) or O(V^3) if using Edmonds method.

However, it can also be reduced to a min cost max flow problem and solved in O(n^3) (by keeping all edges positive and using Dijkstra shortest path).

Why would one use Hungarian method over the flow method?

• co.combinatorics
• graph-theory
• bipartite-graphs
• matching-theory

2 Answers 2

Actually, the two techniques might actually be basically the same. If you read Schrijver's Combinatorial Optimization: Polyhedra and Efficiency , Section 17.2 (where it talks about the Hungarian method), the description of the method is based on using min-cost augmenting paths, then removing a factor of N by using potentials to obtain nonnegative paths so as to use Dijkstra's algorithm.

In more detail... the traditional weight-altering Hungarian method (e.g. as explained by Wikipedia ) is an $O(N^4)$ dual-based algorithm, while Schrijver first explains an $O(N^4)$ primal-based algorithm. He goes on to explain that it can be implemented in $O(N^3)$ time by using potentials so as to use Dijkstra's algorithm in place of Bellman-Ford, obtaining a primal-dual algorithm. However, the $O(N^3)$ dual-based algorithm (e.g., as explained in a sort of confusing way by TopCoder ) seems to be doing much of the same thing. I think the shortest paths manifest as looking for the smallest nonnegative cost edge in each iteration.

• $\begingroup$ Actually, as Schrijver tends to do, he already explains the best insights. This exact correspondence is the subject of section 18.5b, "Dual, primal-dual, primal?" $\endgroup$ –  Dave Pritchard Commented Jan 25, 2016 at 4:13

I would prefer the Hungarian method in cases, where a simpler algorithm and a simpler data structure seem desirable; that could be the case, if only small instances need to be handled or, if a GPU implementation is intended.

Handling m-to-n assignments is also possible with the Hungarian Method via cloning:

if a worker can perform $k$ tasks, then creating $k$ clones of the respective worker does the trick.

if a task requires $k$ workers, then creating $k$ clones of the tasks does the trick.

if w.l.o.g. workers correspond to rows in the assignment matrix and tasks to columns, then cloning is done by creating duplicates of the corresponding rows, resp. columns. It should however be kept in mind, that a solution is not always possible due to shortage of either workers or tasks, but drawing conclusions of such failures (need to hire a worker or send him on vacation or, to create or give up tasks), is a different story.

Actual advice for chosing between the two methods would however better be discussed in a forum dedicated to scientific computing (e.g. http://scicomp.stackexchange.com )

• $\begingroup$ Thanks! Can the Hungarian method be used if each each node can have more than 1 "assignment"? $\endgroup$ –  EugeneMi Commented Oct 30, 2014 at 23:55
• $\begingroup$ @EugeneMi I just added the answer to the multiple assignment problem in an edit to my answer. I hope that is of any help to you. $\endgroup$ –  Manfred Weis Commented Oct 31, 2014 at 7:16

Your Answer

Sign up or log in, post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Not the answer you're looking for? Browse other questions tagged co.combinatorics graph-theory algorithms bipartite-graphs matching-theory or ask your own question .

• Featured on Meta
• Bringing clarity to status tag usage on meta sites
• Join Stack Overflow’s CEO and me for the first Stack IRL Community Event in...

Network flow problem

Author: Aaron Wheeler, Chang Wei, Cagla Deniz Bahadir, Ruobing Shui, Ziqiu Zhang (ChemE 6800 Fall 2020)

• 1 Introduction
• 2.1.1 The Assignment Problem
• 2.1.2 The Transportation Problem
• 2.1.3 The Shortest-Path Problem
• 2.1.4 Maximal Flow Problem
• 2.2.1 Ford–Fulkerson Algorithm
• 3.1 Formulation of the Problem
• 3.2 Solution of the Problem
• 4.1 The Minimum Cost Flow Problem
• 4.2 The Assignment Problem
• 4.3 The Shortest Path Problem
• 5 Conclusion
• 6 References

Introduction

Network flow problems arise in several key instances and applications within society and have become fundamental problems within computer science, operations research, applied mathematics, and engineering. Developments in the approach to tackle these problems resulted in algorithms that became the chief instruments for solving problems related to large-scale systems and industrial logistics. Spurred by early developments in linear programming, the methods for addressing these extensive problems date back several decades and they evolved over time as the use of digital computing became increasingly prevalent in industrial processes. Historically, the first instance of an algorithmic development for the network flow problem came in 1956, with the network simplex method formulated by George Dantzig. [1] A variation of the simplex algorithm that revolutionized linear programming, this method leveraged the combinatorial structure inherent to these types of problems and demonstrated incredibly high accuracy. [2] This method and its variations would go on to define the embodiment of the algorithms and models for the various and distinct network flow problems discussed here.

Theory, Methodology, and Algorithms

Additional constraints of the network flow optimization model place limits on the solution and vary significantly based on the specific type of problem being solved. Historically, the classic network flow problems are considered to be the maximum flow problem and the minimum-cost circulation problem, the assignment problem, bipartite matching problem, transportation problem, and the transshipment problem. [2] The approach to these problems become quite specific based upon the problem’s objective function but can be generalized by the following iterative approach: 1. determining the initial basic feasible solution; 2. checking the optimality conditions (i.e. whether the problem is infeasible, unbounded over the feasible region, optimal solution has been found, etc.); and 3. constructing an improved basic feasible solution if the optimal solution has not been determined. [3]

General Applications

The assignment problem.

Various real-life instances of assignment problems exist for optimization, such as assigning a group of people to different tasks, events to halls with different capacities, rewards to a team of contributors, and vacation days to workers. All together, the assignment problem is a bipartite matching problem in the kernel. [3] In a classical setting, two types of objects of equal amount are  bijective (i.e. they have one-to-one matching), and this tight constraint ensures a perfect matching. The objective is to minimize the cost or maximize the profit of matching, since different items of two types have distinct affinity.

Figure 2 can be viewed as a network. The nodes represent people and tasks, and the edges represent potential assignments between a person and a task. Each task can be completed by any person. However, the person that actually ends up being assigned to the task will be the lone individual who is best suited to complete. In the end, the edges with positive flow values will be the only ones represented in the finalized assignment. [5]

The concise-form formulation of the problem is as follows [3] :

Subject to:

The first constraint captures the requirement of assigning each person  to a single task. The second constraint indicates that each task must be done by exactly one person. The objective function sums up the overall benefits of all assignments.

To see the analogy between the assignment problem and the network flow, we can describe each person supplying a flow of 1 unit and each task demanding a flow of 1 unit, with the benefits over all “channels” being maximized. [3]

A potential issue lies in the branching of the network, specifically an instance where a person splits its one unit of flow into multiple tasks and the objective remains maximized. This shortcoming is allowed by the laws that govern the network flow model, but are unfeasible in real-life instances. Fortunately, since the network simplex method only involves addition and subtraction of a single edge while transferring the basis, which is served by the spanning tree of the flow graph, if the supply (the number of people here) and the demand (the number of tasks here) in the constraints are integers, the solved variables will be automatically integers even if it is not explicitly stated in the problem. This is called the integrality of the network problem, and it certainly applies to the assignment problem. [6]

The Transportation Problem

People first came up with the transportation problem when distributing troops during World War II. [7] Now, it has become a useful model for solving logistics problems, and the objective is usually to minimize the cost of transportation.

Consider the following scenario:

Several quantities should be defined to help formulate the frame of the solution:

Here, the amount of material being delivered and being consumed is bound to the supply and demand constraints:

The objective is to find the minimum cost of transportation, so the cost of each transportation line should be added up, and the total cost should be minimized.

Using the definitions above, the problem can be formulated as such:

The problem and the formulation is adapted from Chapter 8 of the book: Applied Mathematical Programming by Bradley, Hax and Magnanti. [3]

The Shortest-Path Problem

The shortest-path problem can be defined as finding the path that yields the shortest total distance between the origin and the destination. Each possible stop is a node and the paths between these nodes are edges incident to these nodes, where the path distance becomes the weight of the edges. In addition to being the most common and straightforward application for finding the shortest path, this model is also used in various applications depending on the definition of nodes and edges. [3] For example, when each node represents a different object and the edge specifies the cost of replacement, the equipment replacement problem is derived. Moreover, when each node represents a different project and the edge specifies the relative priority, the model becomes a project scheduling problem.

A graph of the general shortest-path problem is depicted as Figure 4:

The first term of the constraint is the total outflow of the node i, and the second term is the total inflow. So, the formulation above could be seen as one unit of flow being supplied by the origin, one unit of flow being demanded by the destination, and no net inflow or outflow at any intermediate nodes. These constraints mandate a flow of one unit, amounting to the active path, from the origin to the destination. Under this constraint, the objective function minimizes the overall path distance from the origin to the destination.

Similarly, the integrality of the network problem applies here, precluding the unreasonable fractioning. With supply and demand both being integer (one here), the edges can only have integer amount of flow in the result solved by simplex method. [6]

In addition, the point-to-point model above can be further extended to other problems. A number of real life scenarios require visiting multiple places from a single starting point. This “Tree Problem” can be modeled by making small adjustments to the original model. In this case, the source node should supply more units of flow and there will be multiple sink nodes demanding one unit of flow. Overall, the objective and the constraint formulation are similar. [4]

Maximal Flow Problem

This problem describes a situation where the material from a source node is sent to a sink node. The source and sink node are connected through multiple intermediate nodes, and the common optimization goal is to maximize the material sent from the source node to the sink node. [3]

The given structure is a piping system. The water flows into the system from the source node, passing through the intermediate nodes, and flows out from the sink node. There is no limitation on the amount of water that can be used as the input for the source node. Therefore, the sink node can accept an unlimited amount of water coming into it. The arrows denote the valid channel that water can flow through, and each channel has a known flow capacity. What is the maximum flow that the system can take?

For the source and sink node, they have net flow that is non-zero:

Flow capacity definition is applied to all nodes (including intermediate nodes, the sink, and the source):

The main constraints for this problem are the transport capacity between each node and the material conservation:

Overall, the net flow out of the source node has to be the same as the net flow into the sink node. This net flow is the amount that should be maximized.

Using the definitions above:

This expression can be further simplified by introducing an imaginary flow from the sink to the source.

By introducing this imaginary flow, the piping system is now closed. The mass conservation constraint now also holds for the source and sink node, so they can be treated as the intermediate nodes. The problem can be rewritten as the following: 

The problem and the formulation are derived from an example in Chapter 8 of the book: Applied Mathematical Programming by Bradley, Hax and Magnanti. [3]

Ford–Fulkerson Algorithm

A broad range of network flow problems could be reduced to the max-flow problem. The most common way to approach the max-flow problem in polynomial time is the Ford-Fulkerson Algorithm (FFA). FFA is essentially a greedy algorithm and it iteratively finds the augmenting s-t path to increase the value of flow. The pathfinding terminates until there is no s-t path present. Ultimately, the max-flow pattern in the network graph will be returned. [8]

Numerical Example and Solution

A Food Distributor Company is farming and collecting vegetables from farmers to later distribute to the grocery stores. The distributor has specific agreements with different third-party companies to mediate the delivery to the grocery stores. In a particular month, the company has 600 ton vegetables to deliver to the grocery store. They have agreements with two third-party transport companies A and B, which have different tariffs for delivering goods between themselves, the distributor, and the grocery store. They also have limits on transport capacity for each path. These delivery points are numbered as shown below, with path 1 being the transport from the Food Distributor Company to the transport company A. The limits and tariffs for each path can be found in the Table 2 below, and the possible transportation connections between the distributor company, the third-party transporters, and the grocery store are shown in the figure below. The distributor companies cannot hold any amount of food, and any incoming food should be delivered to an end point. The distributor company wants to minimize the overall transport cost of shipping 600 tons of vegetables to the grocery store by choosing the optimal path provided by the transport companies. How should the distributor company map out their path and the amount of vegetables carried on each path to minimize cost overall?

This question is adapted from one of the exercise questions in chapter 8 of the book: Applied Mathematical Programming by Bradley, Hax and Magnanti [3] .

Formulation of the Problem

The second step is to write down the constraints. The first constraint ensures that the net amount present in the Transport Company A, which is the deliveries received from path 1 and path 2 minus the transport to Transport Company B should be delivered to the grocery store with path 5. The second constraint ensures this for the Transport Company B. The third and fourth constraints are ensuring that the total amount of vegetables shipping from the Food Distributor Company and the total amount of vegetables delivered to the grocery store are both 600 tons. The constraints 5 to 10 depict the upper limits of the amount of vegetables that can be carried on paths 1 to 6. The final constraint depicts that all variables are non-negative.

Solution of the Problem

This problem can be solved using Simplex Algorithm [11] or with the CPLEX Linear Programming solver in GAMS optimization platform. The steps of the solution using the GAMS platform is as follows:

variables x1,x2,x3,x4,x5,x6,z;

obj.. z=e= 10*x1+12.5*x2+5*x3+7.5*x4+10*x5+20*x6;

Overall, there are 10 constraints in this problem. The constraints 1, and 2 are equations for the paths 5 and 6. The amount carried in path 5 can be found by summing the amount of vegetables incoming to Transport Company A from path 1 and path 4, minus the amount of vegetables leaving Transport Company A with path 3. This can be attributed to the restriction that barrs the companies from keeping any vegetables and requires them to eventually deliver all the incoming produce. The equality 1 ensures that this constraint holds for path 5 and equation 2 ensures it for path 6. A sample of these constraints is written below for path 5:

c1.. x5 =e=x1-x3+x4;

Constraint 3 ensures that the sum of vegetables carried in path 1 and path 2 add to the total of 600 tons of vegetables that leave the Food Distributor Company. Likewise, the constraint 4 ensures that the sum amount of food transported in paths 5 and 6 adds up to 600 tons of vegetables that have to be delivered to the grocery store. A sample of these constraints is written below for the total delivery to the grocery store:

c3.. x5+x6=e=600;

Constraints 5 to 10 should ensure that the amount of food transported in each path should not exceed the maximum capacity depicted in the table. A sample of these constraints is written below for the capacity of path 1:

c5.. x1=l=250;

After listing the variables, objective function and the constraints, the final step is to call the CPLEX solver and set the type of the optimization problem as lp (linear programming). In this case the problem will be solved with a Linear Programming algorithm to minimize the objective (cost) function.

The GAMS code yields the results below:

x1 = 250, x2 = 350, x3 = 0, x4 = 50, x5 = 300, x6 = 300, z =16250.

Real Life Applications

Network problems have many applications in all kinds of areas such as transportation, city design, resource management and financial planning. [6]

There are several special cases of network problems, such as the shortest path problem, minimum cost flow problem, assignment problem and transportation problem. [6] Three application cases will be introduced here.

The Minimum Cost Flow Problem

Minimum cost flow problems are pervasive in real life, such as deciding how to allocate temporal quay crane in container terminals, and how to make optimal train schedules on the same railroad line. [12]

R. Dewil and his group use MCNFP to assist traffic enforcement. [13] Police patrol “hot spots”, which are areas where crashes occur frequently on highways. R. Dewil studies a method intended to estimate the optimal route of hot spots. He describes the time it takes to move the detector to a certain position as the cost, and the number of patrol cars from one node to next as the flow, in order to minimize the total cost. [13]

Dung-Ying Lin studies an assignment problem in which he aims to assign freights to ships and arrange transportation paths along the Northern Sea Route in a manner which yields maximum profit. [14] Within this network  composed of a ship subnetwork and a cargo subnetwork( shown as Figure 12 and Figure 13), each node corresponds to a port at a specific time and each arc represents the movement of a ship or a cargo. Other types of assignment problems are faculty scheduling, freight assignment, and so on.

The Shortest Path Problem

Shortest path problems are also present in many fields, such as transportation, 5G wireless communication, and implantation of the global dynamic routing scheme. [15][16][17]

Qiang Tu and his group studies the constrained reliable shortest path (CRSP) problem for electric vehicles in the urban transportation network. [15] He describes the reliable travel time of path as the objective item, which is made up of planning travel time of path and the reliability item. The group studies the Chicago sketch network consisting of 933 nodes and 2950 links and the Sioux Falls network consisting of 24 nodes and 76 links. The results show that the travelers’ risk attitudes and properties of electric vehicles in the transportation network can have a great influence on the path choice. [15] The study can contribute to the invention of the city navigation system.

Since its inception, the network flow problem has provided humanity with a straightforward and scalable approach for several large-scale challenges and problems. The Simplex algorithm and other computational optimization platforms have made addressing these problems routine, and have greatly expedited efforts for groups concerned with supply-chain and other distribution processes. The formulation of this problem has had several derivations from its original format, but its overall methodology and approach have remained prevalent in several of society’s industrial and commercial processes, even over half a century later. Classical models such as the assignment, transportation, maximal flow, and shortest path problem configurations have found their way into diverse settings, ranging from streamlining oil distribution networks along the gulf coast to arranging optimal scheduling assignments for college students amidst a global pandemic. All in all, the network flow problem and its monumental impact, have made it a fundamental tool for any group that deals with combinatorial data sets. And with the surge in adoption of data-driven models and applications within virtually all industries, the use of the network flow problem approach will only continue to drive innovation and meet consumer demands for the foreseeable future.

1. Karp, R. M. (2008). George Dantzig’s impact on the theory of computation . Discrete Optimization, 5(2), 174-185.

2. Goldberg, A. V. Tardos, Eva, Tarjan, Robert E. (1989). Network Flow Algorithms, Algorithms and Combinatorics . 9. 101-164.

3. Bradley, S. P. Hax, A. C., & Magnanti, T. L. (1977). Network Models. Applied mathematical programming (p. 259). Reading, MA: Addison-Wesley.

4. Chinneck, J. W. (2006). Practical optimization: a gentle introduction. Systems and Computer Engineering . Carleton University, Ottawa. 11.

5. Roy, B. V. Mason, K.(2005). Formulation and Analysis of Linear Programs, Chapter 5 Network Flows .

6. Vanderbei, R. J. (2020). Linear programming: foundations and extensions (Vol. 285) . Springer Nature.

7. Sobel, J. (2014). Linear Programming Notes VIII: The Transportation Problem .

8. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Section 26.2: The Ford–Fulkerson method". Introduction to Algorithms (Second ed.). MIT Press and McGraw–Hill.

9. Jon Kleinberg; Éva Tardos (2006). "Chapter 7: Network Flow". Algorithm Design. Pearson Education.

10. Ford–Fulkerson algorithm . Retrieved December 05, 2020.

11. Hu, G. (2020, November 19). Simplex algorithm . Retrieved November 22, 2020.

12. Altınel, İ. K., Aras, N., Şuvak, Z., & Taşkın, Z. C. (2019). Minimum cost noncrossing flow problem on layered networks . Discrete Applied Mathematics, 261, 2-21.

13. Dewil, R., Vansteenwegen, P., Cattrysse, D., & Van Oudheusden, D. (2015). A minimum cost network flow model for the maximum covering and patrol routing problem . European Journal of Operational Research, 247(1), 27-36.

14. Lin, D. Y., & Chang, Y. T. (2018). Ship routing and freight assignment problem for liner shipping: Application to the Northern Sea Route planning problem . Transportation Research Part E: Logistics and Transportation Review, 110, 47-70.

15. Tu, Q., Cheng, L., Yuan, T., Cheng, Y., & Li, M. (2020). The Constrained Reliable Shortest Path Problem for Electric Vehicles in the Urban Transportation Network . Journal of Cleaner Production, 121130.

16. Guo, Y., Li, S., Jiang, W., Zhang, B., & Ma, Y. (2017). Learning automata-based algorithms for solving the stochastic shortest path routing problems in 5G wireless communication . Physical Communication, 25, 376-385.

17. Haddou, N. B., Ez-Zahraouy, H., & Rachadi, A. (2016). Implantation of the global dynamic routing scheme in scale-free networks under the shortest path strategy . Physics Letters A, 380(33), 2513-2517.

Navigation menu

• Interview Problems on Graph
• Practice Graph
• MCQs on Graph
• Graph Tutorial
• Graph Representation
• Graph Properties
• Types of Graphs
• Graph Applications
• BFS on Graph
• DFS on Graph
• Graph VS Tree
• Transpose Graph
• Dijkstra's Algorithm
• Minimum Spanning Tree
• Prim’s Algorithm
• Topological Sorting
• Floyd Warshall Algorithm
• Strongly Connected Components
• Advantages & Disadvantages

Max Flow Problem Introduction

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

Another popular algorithm for solving the max flow problem is the Edmonds-Karp algorithm, which is a variant of the Ford-Fulkerson algorithm that uses breadth-first search to find augmenting paths, and thus can be more efficient in some cases.

Advantages:

• The max flow problem is a flexible and powerful modeling tool that can be used to represent a wide variety of real-world situations.
• 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.
• The max flow problem has many interesting theoretical properties and connections to other areas of mathematics, such as linear programming and combinatorial optimization.

Disadvantages:

• 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.
• 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.

Each edge is labeled with capacity, the maximum amount of stuff that it can carry. The goal is to figure out how much stuff can be pushed from the vertex s(source) to the vertex t(sink). 

maximum flow possible is : 23 

Following are different approaches to solve the problem :   

1. Naive Greedy Algorithm Approach (May not produce an optimal or correct result) Greedy approach to the maximum flow problem is to start with the all-zero flow and greedily produce flows with ever-higher value. The natural way to proceed from one to the next is to send more flow on some path from s to t How Greedy approach work to find the maximum flow :

Note that the path search just needs to determine whether or not there is an s-t path in the subgraph of edges e with f(e) < C(e). This is easily done in linear time using BFS or DFS.

After removing all useless edge from graph it’s look like

For above graph there is no path from source to sink so maximum flow : 3 unit But maximum flow is 5 unit. to over come from this issue we use residual Graph.  

Below are the programs to implement the above concept:

2. Residual Graphs

backward edge : ( f(e) ) and forward edge : ( C(e) – f(e) ) We need a way of formally specifying the allowable “undo” operations. This motivates the following simple but important definition, of a residual network. The idea is that, given a graph G and a flow f in it, we form a new flow network G f that has the same vertex set of G and that has two edges for each edge of G. An edge e = (1,2) of G that carries flow f(e) and has capacity C(e) (for above image ) spawns a “forward edge” of G f with capacity C(e)-f(e) (the room remaining) and a “backward edge” (2,1) of G f with capacity f(e) (the amount of previously routed flow that can be undone). source(s)- sink(t) paths with f(e) < C(e) for all edges, as searched for by the naive greedy algorithm, corresponding to the special case of s-t paths of G f that comprise only forward edges. 

The idea of residual graph is used The Ford-Fulkerson and Dinic’s algorithms 

Source : http://theory.stanford.edu/~tim/w16/l/l1.pdf  

Please Login to comment...

Similar reads.

• Best Twitch Extensions for 2024: Top Tools for Viewers and Streamers
• Discord Emojis List 2024: Copy and Paste
• Best Adblockers for Twitch TV: Enjoy Ad-Free Streaming in 2024
• PS4 vs. PS5: Which PlayStation Should You Buy in 2024?
• 10 Best Free VPN Services in 2024

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Solving assignment problem using min-cost-flow ¶

The assignment problem has two equivalent statements:

• Given a square matrix $A[1..N, 1..N]$ , you need to select $N$ elements in it so that exactly one element is selected in each row and column, and the sum of the values of these elements is the smallest.
• There are $N$ orders and $N$ machines. The cost of manufacturing on each machine is known for each order. Only one order can be performed on each machine. It is required to assign all orders to the machines so that the total cost is minimized.

Here we will consider the solution of the problem based on the algorithm for finding the minimum cost flow (min-cost-flow) , solving the assignment problem in $\mathcal{O}(N^3)$ .

Description ¶

Let's build a bipartite network: there is a source $S$ , a drain $T$ , in the first part there are $N$ vertices (corresponding to rows of the matrix, or orders), in the second there are also $N$ vertices (corresponding to the columns of the matrix, or machines). Between each vertex $i$ of the first set and each vertex $j$ of the second set, we draw an edge with bandwidth 1 and cost $A_{ij}$ . From the source $S$ we draw edges to all vertices $i$ of the first set with bandwidth 1 and cost 0. We draw an edge with bandwidth 1 and cost 0 from each vertex of the second set $j$ to the drain $T$ .

We find in the resulting network the maximum flow of the minimum cost. Obviously, the value of the flow will be $N$ . Further, for each vertex $i$ of the first segment there is exactly one vertex $j$ of the second segment, such that the flow $F_{ij}$ = 1. Finally, this is a one-to-one correspondence between the vertices of the first segment and the vertices of the second part, which is the solution to the problem (since the found flow has a minimal cost, then the sum of the costs of the selected edges will be the lowest possible, which is the optimality criterion).

The complexity of this solution of the assignment problem depends on the algorithm by which the search for the maximum flow of the minimum cost is performed. The complexity will be $\mathcal{O}(N^3)$ using Dijkstra or $\mathcal{O}(N^4)$ using Bellman-Ford . This is due to the fact that the flow is of size $O(N)$ and each iteration of Dijkstra algorithm can be performed in $O(N^2)$ , while it is $O(N^3)$ for Bellman-Ford.

Implementation ¶

The implementation given here is long, it can probably be significantly reduced. It uses the SPFA algorithm for finding shortest paths.

• Daili01 (75.89%)
• prpr (12.5%)
• Oleksandr Kulkov (7.14%)
• Shadab Zafar (2.68%)
• Jakob Kogler (0.89%)
• Hasan-Mesbaul-Ali-Taher (0.89%)

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Lower bounds on max-flow and assignment problems

As far as I know, all existing strongly polynomial algorithms for flows and assignment problem have $\Omega(V^3)$ complexity in the arithmetic model (assuming the graph is dense). I'm interested in the arithmetic model of computation, where each arithmetic operation on two numbers takes $O(1)$ time regardless of the size of the numbers, not the RAM model.

Is there any theoretical result or conjecture that explains this? I know that there are conjectured complexity lower bounds for problems in P based on 3SUM/APSP/some other problems, but I've never seen them applied to flow-related problems.

• complexity-theory
• network-flow
• lower-bounds
• assignment-problem

Know someone who can answer? Share a link to this question via email , Twitter , or Facebook .

Your answer, sign up or log in, post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Browse other questions tagged complexity-theory network-flow lower-bounds assignment-problem or ask your own question .

• Featured on Meta
• Join Stack Overflow’s CEO and me for the first Stack IRL Community Event in...
• Bringing clarity to status tag usage on meta sites

Hot Network Questions

• How does registration work in a modern accordion?
• Pólya trees counted efficiently
• Model reduction in linear regression by stepwise elimination of predictors with "non-significant" coefficients
• Could a lawyer agree not to take any further cases against a company?
• How long should a wooden construct burn (and continue to take damage) until it burns out (and stops doing damage)
• How cheap would rocket fuel have to be to make Mars colonization feasible (according to Musk)?
• Starting with 2014 "+" signs and 2015 "−" signs, you delete signs until one remains. What’s left?
• Do US universities invite faculty applicants from outside the US for an interview?
• How high does the ocean tide rise every 90 minutes due to the gravitational pull of the space station?
• A short story called "Of Jovian Build" , who wrote it?
• What is the EPSG for Czechia (Czech) DMR 5G Lidar Data?
• Movie / episode where a spaceplane is stuck in orbit
• Why does my LED bulb light up dimly when I touch it?
• Textile Innovations of Pachyderms: Clothing Type
• Can the planet Neptune be seen from Earth with binoculars?
• Can population variance from multiple studies be averaged to use for a sample size calculation?
• "Vector Character" in Whitehead's Process and Reality
• How to change the robotic voice in Foliate ebook reader and other apps using speech dispatcher?
• How to raise and lower indices as a physicist would handle it?
• How does a miner create multiple outputs in a coinbase transaction?
• Flats on gravel with GP5000 - what am I doing wrong?
• Potential Syscall Note Loophole?
• Are there many more verbs like 'abflauen' where the basic infinitive 'flauen' does not exist?
• When a mass crosses a black hole event horizon does the horizon radius get larger closer to the mass or does it increase equally everywhere?

• Stack Overflow for Teams Where developers & technologists share private knowledge with coworkers
• Advertising & Talent Reach devs & technologists worldwide about your product, service or employer brand
• OverflowAI GenAI features for Teams
• OverflowAPI Train & fine-tune LLMs
• Labs The future of collective knowledge sharing
• About the company Visit the blog

Collectives™ on Stack Overflow

Find centralized, trusted content and collaborate around the technologies you use most.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Get early access and see previews of new features.

Assigning jobs to people using Maximum Flow, harder version

I am self studying max flow and there was this problem:

the original problem is

Suppose we have a list of jobs

{J1, J1,..., Jm}

and a list of people that have applied for them

{P1, P2, P3,...,Pn}

each person have different interests and some of them have applied for multiple jobs (each person has a list of jobs they can do)

nobody is allowed to do more than 3 jobs.

I understand this solution, but

the harder version of the problem

what if these conditions are added?

the first 3 conditions of the easy version (lists of jobs and persons and each person has a list of interests or abilities) are still the same

the compony is employing only Vi persons for job Ji

the compony wants to employ as many people as possible

there is no limitations for the number of jobs a person is allowed to do.

What difference should I make in the graph so that my solution can satisfy those conditions as well?or if I need a different approach please tell me.

before anyone say anything, this is not homework. It's just self study, but I am studying Maximum flow and the problem was in that area so the solution should use Maximum flow.

• graph-algorithm
• network-flow
• ford-fulkerson

• What about changing jobs with people in the graph and then instead of having 3 capacities on the edges from source to the jobs (now in the place of people in the graph below), considering Vi capacity? Will that work? –  Peggy Commented Jun 5, 2013 at 9:58

For multiple persons for a single job:

The edge from Ji to t will have the capacity equal to the number of people for that job. E.g. If job #1 can have three people, this translates to a capacity of three for the edge from J1 to t .

For the requirement of hiring as many people as possible:

I don't think this is possible with a single flow-graph. Here is an algorithm for how it could be done:

• Run the flow-algorithm once.
• Try to decrease the incoming capacity to one below the current flow-rate.
• Run the flow-algorithm again.
• While this does not decrease the total flow, repeat from (2.1.).
• Increase the capacity by one, to restore the maximum flow.
• Until no further persons gets added, repeat from (2.).  

For no limitation on number of jobs:

The edges from s to Pi will have a maximum flow equal the number of applicable jobs for that person.

Your Answer

Reminder: Answers generated by artificial intelligence tools are not allowed on Stack Overflow. Learn more

Sign up or log in

Post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Not the answer you're looking for? Browse other questions tagged algorithm graph graph-algorithm network-flow ford-fulkerson or ask your own question .

• The Overflow Blog
• The hidden cost of speed
• The creator of Jenkins discusses CI/CD and balancing business with open source
• Featured on Meta
• Bringing clarity to status tag usage on meta sites
• Join Stack Overflow’s CEO and me for the first Stack IRL Community Event in...
• Feedback requested: How do you use tag hover descriptions for curating and do...
• Staging Ground Reviewer Motivation
• What does a new user need in a homepage experience on Stack Overflow?

Hot Network Questions

• Pólya trees counted efficiently
• Advanced Composite Solar Sail (ACS3) Orbit
• How would you read this time change with the given note equivalence?
• Could they free up a docking port on ISS by undocking the emergency vehicle and letting it float next to the station for a little while
• Job suffering for the misdeeds of his ancestors
• Is a ring endomorphism determined by its right inverse?
• Beatles reference in parody story from the 1980s
• What is the Kronecker product of two 1D vectors?
• Flats on gravel with GP5000 - what am I doing wrong?
• How to fold or expand the wingtips on Boeing 777?
• Why wasn't Randall Stevens caught?
• \documentclass in separate .tex file
• Is this host and 'parasite' interaction feasible?
• Do US universities invite faculty applicants from outside the US for an interview?
• Bathroom fan venting options
• subtle racism in the lab
• Generate all the free polyominoes who's width and height is no larger than 8
• Is a continuous real function with vanishing derivative in all but countably many points constant?
• Parsing and processing "resolvectl statistics" output using awk
• Electromagnetic Eigenvalue problem in FEM yielding spurious solutions
• What are the steps to write a book?
• Why does each leg of my 240V outlet measure 125V to ground, but 217V across the hot wires?
• What do these expressions mean in NASA's Steve Stitch's brief Starliner undocking statement?
• Can Noun Phrases qualify Latin adjectives