weighted graph assignment problem

Reset password New user? Sign up

Existing user? Log in

Hungarian Maximum Matching Algorithm

Already have an account? Log in here.

The Hungarian matching algorithm , also called the Kuhn-Munkres algorithm, is a $O\big(|V|^3\big)$ algorithm that can be used to find maximum-weight matchings in bipartite graphs , which is sometimes called the assignment problem . A bipartite graph can easily be represented by an adjacency matrix , where the weights of edges are the entries. Thinking about the graph in terms of an adjacency matrix is useful for the Hungarian algorithm.

A matching corresponds to a choice of 1s in the adjacency matrix, with at most one 1 in each row and in each column.

The Hungarian algorithm solves the following problem:

In a complete bipartite graph $G$, find the maximum-weight matching. (Recall that a maximum-weight matching is also a perfect matching.)

This can also be adapted to find the minimum-weight matching.

Say you are having a party and you want a musician to perform, a chef to prepare food, and a cleaning service to help clean up after the party. There are three companies that provide each of these three services, but one company can only provide one service at a time (i.e. Company B cannot provide both the cleaners and the chef). You are deciding which company you should purchase each service from in order to minimize the cost of the party. You realize that is an example of the assignment problem, and set out to make a graph out of the following information: $\quad$ Company$\quad$ $\quad$ Cost for Musician$\quad$ $\quad$ Cost for Chef$\quad$ $\quad$ Cost for Cleaners$\quad$ $\quad$ Company A$\quad$ $\quad$ $108$\quad$ $\quad$ $125$\quad$ $\quad$ $150$\quad$ $\quad$ Company B$\quad$ $\quad$ $150$\quad$ $\quad$ $135$\quad$ $\quad$ $175$\quad$ $\quad$ Company C$\quad$ $\quad$ $122$\quad$ $\quad$ $148$\quad$ $\quad$ $250$\quad$ Can you model this table as a graph? What are the nodes? What are the edges? Show Answer The nodes are the companies and the services. The edges are weighted by the price.

What are some ways to solve the problem above? Since the table above can be thought of as a $3 \times 3$ matrix, one could certainly solve this problem using brute force, checking every combination and seeing what yields the lowest price. However, there are $n!$ combinations to check, and for large $n$, this method becomes very inefficient very quickly.

The Hungarian Algorithm Using an Adjacency Matrix

The hungarian algorithm using a graph.

With the cost matrix from the example above in mind, the Hungarian algorithm operates on this key idea: if a number is added to or subtracted from all of the entries of any one row or column of a cost matrix, then an optimal assignment for the resulting cost matrix is also an optimal assignment for the original cost matrix.

The Hungarian Method [1] Subtract the smallest entry in each row from all the other entries in the row. This will make the smallest entry in the row now equal to 0. Subtract the smallest entry in each column from all the other entries in the column. This will make the smallest entry in the column now equal to 0. Draw lines through the row and columns that have the 0 entries such that the fewest lines possible are drawn. If there are $n$ lines drawn, an optimal assignment of zeros is possible and the algorithm is finished. If the number of lines is less than $n$, then the optimal number of zeroes is not yet reached. Go to the next step. Find the smallest entry not covered by any line. Subtract this entry from each row that isn’t crossed out, and then add it to each column that is crossed out. Then, go back to Step 3.

Solve for the optimal solution for the example in the introduction using the Hungarian algorithm described above. Here is the initial adjacency matrix: Subtract the smallest value in each row from the other values in the row: Now, subtract the smallest value in each column from all other values in the column: Draw lines through the row and columns that have the 0 entries such that the fewest possible lines are drawn: There are 2 lines drawn, and 2 is less than 3, so there is not yet the optimal number of zeroes. Find the smallest entry not covered by any line. Subtract this entry from each row that isn’t crossed out, and then add it to each column that is crossed out. Then, go back to Step 3. 2 is the smallest entry. First, subtract from the uncovered rows: Now add to the covered columns: Now go back to step 3, drawing lines through the rows and columns that have 0 entries: There are 3 lines (which is $n$), so we are done. The assignment will be where the 0's are in the matrix such that only one 0 per row and column is part of the assignment. Replace the original values: The Hungarian algorithm tells us that it is cheapest to go with the musician from company C, the chef from company B, and the cleaners from company A. We can verify this by brute force. 108 + 135 + 250 = 493 108 + 148 + 175 = 431 150 + 125 + 250 = 525 150 + 148 + 150 = 448 122 + 125 + 175 = 422 122 + 135 + 150 = 407. We can see that 407 is the lowest price and matches the assignment the Hungarian algorithm determined. $_\square$

The Hungarian algorithm can also be executed by manipulating the weights of the bipartite graph in order to find a stable, maximum (or minimum) weight matching. This can be done by finding a feasible labeling of a graph that is perfectly matched, where a perfect matching is denoted as every vertex having exactly one edge of the matching.

How do we know that this creates a maximum-weight matching?

A feasible labeling on a perfect match returns a maximum-weighted matching. Suppose each edge $e$ in the graph $G$ connects two vertices, and every vertex $v$ is covered exactly once. With this, we have the following inequality: \[w(M’) = \sum_{e\ \epsilon\ E} w(e) \leq \sum_{e\ \epsilon\ E } \big(l(e_x) + l(e_y)\big) = \sum_{v\ \epsilon\ V} l(v),\] where $M’$ is any perfect matching in $G$ created by a random assignment of vertices, and $l(x)$ is a numeric label to node $x$. This means that $\sum_{v\ \epsilon\ V}\ l(v)$ is an upper bound on the cost of any perfect matching. Now let $M$ be a perfect match in $G$, then \[w(M) = \sum_{e\ \epsilon\ E} w(e) = \sum_{v\ \epsilon\ V}\ l(v).\] So $w(M’) \leq w(M)$ and $M$ is optimal. $_\square$

Start the algorithm by assigning any weight to each individual node in order to form a feasible labeling of the graph $G$. This labeling will be improved upon by finding augmenting paths for the assignment until the optimal one is found.

A feasible labeling is a labeling such that

$l(x) + l(y) \geq w(x,y)\ \forall x \in X, y \in Y$, where $X$ is the set of nodes on one side of the bipartite graph, $Y$ is the other set of nodes, $l(x)$ is the label of $x$, etc., and $w(x,y)$ is the weight of the edge between $x$ and $y$.

A simple feasible labeling is just to label a node with the number of the largest weight from an edge going into the node. This is certain to be a feasible labeling because if $A$ is a node connected to $B$, the label of $A$ plus the label of $B$ is greater than or equal to the weight $w(x,y)$ for all $y$ and $x$.

A feasible labeling of nodes, where labels are in red [2] .

Imagine there are four soccer players and each can play a few positions in the field. The team manager has quantified their skill level playing each position to make assignments easier.

How can players be assigned to positions in order to maximize the amount of skill points they provide?

The algorithm starts by labeling all nodes on one side of the graph with the maximum weight. This can be done by finding the maximum-weighted edge and labeling the adjacent node with it. Additionally, match the graph with those edges. If a node has two maximum edges, don’t connect them.

Although Eva is the best suited to play defense, she can't play defense and mid at the same time!

If the matching is perfect, the algorithm is done as there is a perfect matching of maximum weights. Otherwise, there will be two nodes that are not connected to any other node, like Tom and Defense. If this is the case, begin iterating.

Improve the labeling by finding the non-zero label vertex without a match, and try to find the best assignment for it. Formally, the Hungarian matching algorithm can be executed as defined below:

The Hungarian Algorithm for Graphs [3] Given: the labeling $l$, an equality graph $G_l = (V, E_l)$, an initial matching $M$ in $G_l$, and an unmatched vertex $u \in V$ and $u \notin M$ Augmenting the matching A path is augmenting for $M$ in $G_l$ if it alternates between edges in the matching and edges not in the matching, and the first and last vertices are free vertices , or unmatched, in $M$. We will keep track of a candidate augmenting path starting at the vertex $u$. If the algorithm finds an unmatched vertex $v$, add on to the existing augmenting path $p$ by adding the $u$ to $v$ segment. Flip the matching by replacing the edges in $M$ with the edges in the augmenting path that are not in $M$ $($in other words, the edges in $E_l - M).$ Improving the labeling $S \subseteq X$ and $T \subseteq Y,$ where $S$ and $T$ represent the candidate augmenting alternating path between the matching and the edges not in the matching. Let $N_l(S)$ be the neighbors to each node that is in $S$ along edges in $E_l$ such that $N_l(S) = \{v|\forall u \in S: (u,v) \in E_l\}$. If $N_l(S) = T$, then we cannot increase the size of the alternating path (and therefore can't further augment), so we need to improve the labeling. Let $\delta_l$ be the minimum of $l(u) + l(v) - w(u,v)$ over all of the $u \in S$ and $v \notin T$. Improve the labeling $l$ to $l'$: If $r \in S,$ then $l'(r) = l(r) - \delta_l,$ If $r \in T,$ then $l'(r) = l(r) + \delta_l.$ If $r \notin S$ and $r \notin T,$ then $l'(r) = l(r).$ $l'$ is a valid labeling and $E_l \subset E_{l'}.$ Putting it all together: The Hungarian Algorithm Start with some matching $M$, a valid labeling $l$, where $l$ is defined as the labelling $\forall x \in X, y \in Y| l(y) = 0, l(x) = \text{ max}_{y \in Y}(w\big(x, y)\big)$. Do these steps until a perfect matching is found $($when $M$ is perfect$):$ (a) Look for an augmenting path in $M.$ (b) If an augmenting path does not exist, improve the labeling and then go back to step (a).

Each step will increase the size of the matching $M$ or it will increase the size of the set of labeled edges, $E_l$. This means that the process will eventually terminate since there are only so many edges in the graph $G$. [4]

When the process terminates, $M$ will be a perfect matching. By the Kuhn-Munkres theorem , this means that the matching is a maximum-weight matching.

The algorithm defined above can be implemented in the soccer scenario. First, the conflicting node is identified, implying that there is an alternating tree that must be reconfigured.

There is an alternating path between defense, Eva, mid, and Tom.

To find the best appropriate node, find the minimum $\delta_l$, as defined in step 4 above, where $l_u$ is the label for player $u,$ $l_v$ is the label for position $v,$ and $w_{u, v}$ is the weight on that edge.

The $\delta_l$ of each unmatched node is computed, where the minimum is found to be a value of 2, between Tom playing mid $(8 + 0 – 6 = 2).$

The labels are then augmented and the new edges are graphed in the example. Notice that defense and mid went down by 2 points, whereas Eva’s skillset got back two points. However, this is expected as Eva can't play in both positions at once.

Augmenting path leads to relabeling of nodes, which gives rise to the maximum-weighted path.

These new edges complete the perfect matching of the graph, which implies that a maximum-weighted graph has been found and the algorithm can terminate.

The complexity of the algorithm will be analyzed using the graph-based technique as a reference, yet the result is the same as for the matrix-based one.

Algorithm analysis [3] At each $a$ or $b$ step, the algorithm adds one edge to the matching and this happens $O\big(|V|\big)$ times. It takes $O\big(|V|\big)$ time to find the right vertex for the augmenting (if there is one at all), and it is $O\big(|V|\big)$ time to flip the matching. Improving the labeling takes $O\big(|V|\big)$ time to find $\delta_l$ and to update the labelling accordingly. We might have to improve the labeling up to $O\big(|V|\big)$ times if there is no augmenting path. This makes for a total of $O\big(|V|^2\big)$ time. In all, there are $O\big(|V|\big)$ iterations each taking $O\big(|V|\big)$ work, leading to a total running time of $O\big(|V|^3\big)$.

Matching Algorithms
Bruff, D. The Assignment Problem and the Hungarian Method . Retrieved June 26, 2016, from http://www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf
Golin, M. Bipartite Matching &amp; the Hungarian Method . Retrieved Retrieved June 26th, 2016, from http://www.cse.ust.hk/~golin/COMP572/Notes/Matching.pdf
Grinman, A. The Hungarian Algorithm for Weighted Bipartite Graphs . Retrieved June 26, 2016, from http://math.mit.edu/~rpeng/18434/hungarianAlgorithm.pdf
Golin, M. Bipartite Matching & the Hungarian Method . Retrieved June 26, 2016, from http://www.cse.ust.hk/~golin/COMP572/Notes/Matching.pdf

Problem Loading...

Note Loading...

Set Loading...

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.

Assignment Problem With Weighted Bipartite Graph

I have the following problem:

Given $n$ workers and $n$ tasks I have to assign a worker to each task where each worker has a time to get to the task, and each task has a preparation time. for example, task 1 preparation time is 10 minutes, it will take worker A 2 minutes to get there, 5 minutes for worker B, and 7 minutes for worker C.

My objective is to assign workers such that the waiting time is minimised.

I modelled it to a Weighted Bipartite Graph

Where each edge has a weight and each blue node (task) has a negative weight and we need to assign a worker such that the total cost will be as close to zero

Which algorithms should I look into to solve this?

optimization
assignment-problem

$\begingroup$ Welcome to OR.SE. It might be modelled as a GAP (Generalized assignment problem) and exact/heuristic methods could be applied to solve that. $\endgroup$ – A.Omidi Commented Feb 17, 2021 at 19:48
$\begingroup$ Why is this not just a plain assignment problem? Assuming that task preparation requires that the worker be present,the weight of arc (i,j) would be the sum of travel time for worker i to reach task j plus prep time of task j. $\endgroup$ – prubin ♦ Commented Feb 17, 2021 at 22:34
$\begingroup$ @newhere Is the number of tasks equal to the number of workers? both mentioned in the question using $n$. $\endgroup$ – Oguz Toragay Commented Feb 18, 2021 at 1:20
$\begingroup$ What I understand is that preparation times are fixed, no matter which worker is assigned. So what is the benefit of including the preparation times into the model, if all of them are to be done? $\endgroup$ – Mostafa Commented Feb 18, 2021 at 2:50
$\begingroup$ @Mostafa what I understand is either task is waiting for the worker or the worker waits for the task to be prepared. The summation of all these waiting times needs to be minimized. $\endgroup$ – Oguz Toragay Commented Feb 18, 2021 at 3:09

From the comments I found that your problem can be described by

a setup time $s_j$ for process $j$
a travel time $c_{ij}$ for worker $i$ to process $j$

Then the waiting time that we get when assigning worker $i$ to process $j$ is given by $w_{ij}:=|s_j-c_{ij}|$ .

Using $w_{ij}$ as your new weights of the assignments you can use any classic assignement algorithm you want to solve this. For example you could use the following LP, which happens to always have an integral optimal solution.

\begin{align} \min \sum_{i,j} w_{ij}x_{ij}\\ \sum_i x_{ij} &= 1 &\forall j\\ \sum_j x_{ij} &=1 &\forall i \\ 0\leq x_{ij} &\leq 1 \end{align}

If this turns out to be too slow you could look into min cost flows on bipartite graphs.

Your Answer

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 optimization assignment-problem or ask your own question .

Featured on Meta
Upcoming sign-up experiments related to tags

Hot Network Questions

Where does someone go with Tzara'as if they are dwelling in a Ir Miklat?
What is the translation of misgendering in French?
Is it this limit impossible or not exists?
No simple group or order 756 : Burnside's proof
How do guitarists remember what note each string represents when fretting?
How are "pursed" and "rounded" synonymous?
Is the FOCAL syntax for Alphanumeric Numbers ("0XYZ") documented anywhere?
Sangaku problem involving eight circles
Is arxiv strictly for new stuff?
How to bid a very strong hand with values in only 2 suits?
Google Search Console reports "Page with redirect" as "errors", are they?
Do capacitor packages make a difference in MLCCs?
Is the zero vector necessary to do quantum mechanics?
What type of black color text for brochure print in CMYK?
Why potential energy is not considered in the internal energy of diatomic molecules?
Is it unfair to retroactively excuse a student for absences?
Do I need to indicate 'solo' for wind/brass instruments in shared staff?
How to produce this table: Probability datatable with multirow
What is the term for when a hyperlink maliciously opens different URL from URL displayed when hovered over?
Geometry question about a six-pack of beer
Integration of the product of two exponential functions
How to determine if gravity is roughly linear?
Is Légal’s reported “psychological trick” considered fair play or unacceptable conduct under FIDE rules?
Visit USA via land border for French citizen

Assignment Problem

1955; Kuhn 1957; Munkres

Reference work entry
Cite this reference work entry

Samir Khuller 2

364 Accesses

Keywords and Synonyms

Weighted bipartite matching

Problem Definition

Assume that a complete bipartite graph, $ { G(X,Y,X \times Y) } $ , with weights w ( x ,  y ) assigned to every edge ( x ,  y ) is given. A matching M is a subset of edges so that no two edges in M have a common vertex. A perfect matching is one in which all the nodes are matched. Assume that $ { |X|=|Y|=n } $ . The weighted matching problem is to find a matching with the greatest total weight, where $ { w(M)=\sum_{e \in M} w(e) } $ . Since G is a complete bipartite graph, it has a perfect matching. An algorithm that solves the weighted matching problem is due to Kuhn [ 4 ] and Munkres [ 6 ]. Assume that all edge weights are nonnegative.

Key Results

Define a feasible vertex labeling ℓ as a mapping from the set of vertices in G to the reals, where

Call $ { \ell(x) } $ the label of vertex x . It is easy to compute a feasible vertex labeling as follows:

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

Access this chapter

Get 10 units per month
Download Article/Chapter or Ebook
1 Unit = 1 Article or 1 Chapter
Cancel anytime
Available as PDF
Read on any device
Instant download
Own it forever
Available as EPUB and PDF

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

This is the structure of explored edges when one starts BFS simultaneously from all free nodes in S . When one reaches a matched node in T , one only explores the matched edge; however, all edges incident to nodes in S are explored.

Author information

Authors and affiliations.

Department of Computer Science, University of Maryland, College Park, MD, USA

Samir Khuller

You can also search for this author in PubMed Google Scholar

Editor information

Editors and affiliations.

Department of Electrical Engineering and Computer ScienceMcCormick School of Engineering and Applied Science, Northwestern University, Evanston, IL, 60208, USA

Ming-Yang Kao Professor of Computer Science

Rights and permissions

Reprints and permissions

Copyright information

About this entry

Cite this entry.

Khuller, S. (2008). Assignment Problem. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-30162-4_35

Download citation

DOI : https://doi.org/10.1007/978-0-387-30162-4_35

Publisher Name : Springer, Boston, MA

Print ISBN : 978-0-387-30770-1

Online ISBN : 978-0-387-30162-4

eBook Packages : Computer Science Reference Module Computer Science and Engineering

Share this entry

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

Publish with us

Policies and ethics

Find a journal
Track your research

IMAGES

Solved WEIGHTED GRAPHS Directions. Solve using the greedy
Solved Consider the following weighted graph with 9 vertices
Figure: Assignment Problem as Weighted Bipartite Graph
Solved Let the length of a path in a weighted graph be the
Solved Consider the following weighted, directed graph,
Data Structure Fundamentals

VIDEO

Traveling Salesman Problem| NP- Class Problem
3a Weighted Assignment Problems
𝗪𝗲𝗶𝗴𝗵𝘁𝗲𝗱 𝗚𝗿𝗮𝗽𝗵𝘀
Lec9/Graph Theory/Weighted Graph
Blitzer Thinking Mathematically Ch 15 Ex 15
DP-WeightedInterval1.mov

COMMENTS

7.13 Assignment Problem - Princeton University
Assignment problem. Input: weighted, complete bipartite graph G = (L ! R, E) with |L| = |R|. Goal: find a perfect matching of min weight. 1 2 3 4 5 1' 2' 3' 4' 5'. Min cost perfect matching M = { 1 -2', 2-3', 3-5', 4-1', 5-4' } cost(M) = 8 + 7 + 10 + 8 + 11 = 44 389 150 407 6 913 0 8 1320 175 9. 3.
Assignment problem - Wikipedia
The assignment problem consists of finding, in a weighted bipartite graph, a matching of a given size, in which the sum of weights of the edges is minimum. If the numbers of agents and tasks are equal, then the problem is called balanced assignment. Otherwise, it is called unbalanced assignment. [1] If the total cost of the assignment for all ...
Bipartite Matching & the Hungarian Method - Columbia University
The Assignment Problem: Let G be a (complete) weighted bipartite graph. The Assignment problem is to ﬁnd a max-weight match-ing in G. A Perfect Matching is an M in which every vertex is adjacent to some edge in M. A max-weight matching is perfect. Max-Flow reduction dosn’t work in presence of weights.
Hungarian Maximum Matching Algorithm | Brilliant Math ...
The Hungarian matching algorithm, also called the Kuhn-Munkres algorithm, is a $O\big(|V|^3\big)$ algorithm that can be used to find maximum-weight matchings in bipartite graphs, which is sometimes called the assignment problem.
Lecture 8: Assignment Algorithms - University of Connecticut
Assignment problem. Also known as weighted bipartite matching problem. Bipartite graph. Has two sets of nodes , ⇒ = ∪. And a set of edges connecting them. A matching on a bipartite graph G = (S, T, E) is a subset of edges ∈ ∋ no two edges in are incident to the same node. Nodes 1, 2, 3, 4. Node of are matched or covered.
Assignment Problem With Weighted Bipartite Graph
My objective is to assign workers such that the waiting time is minimised. I modelled it to a Weighted Bipartite Graph. Where each edge has a weight and each blue node (task) has a negative weight and we need to assign a worker such that the total cost will be as close to zero.
The Assignment Problem - Emory University
The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics. In an assignment problem , we must find a maximum matching that has the minimum weight in a weighted bipartite graph .
The Dynamic Hungarian Algorithm for the Assignment Problem ...
The assignment problem, also known as the maximum weighted bipartite matching problem, is a widely-studied problem applicable to many domains [2]. It can be stated as follows: given a set of workers, a set of jobs, and a set of ratings indicating how well each worker can perform each job, determine the best possible assignment of workers
The Assignment Problem — An example - ETH Z
bipartite graph? In the maximum weighted matching problem a non-negative weight wi;j is assigned to each edge xiyj of Kn;n and we seek a perfect matching M to maximize the total weight w(M)= P e2M w(e). With these weights, a (weighted) cover is a choice of labels u1;:::;un and v1;:::;vn, such that ui +vj wi;j for all i;j. The cost c(u;v) of a ...
Assignment Problem | SpringerLink
Problem Definition. Assume that a complete bipartite graph, \ ( { G (X,Y,X \times Y) } \), with weights w ( x , y) assigned to every edge ( x , y) is given. A matching M is a subset of edges so that no two edges in M have a common vertex. A perfect matching is one in which all the nodes are matched. Assume that \ ( { |X|=|Y|=n } \).