How to Use the Hungarian Algorithm

The Hungarian algorithm allows a "minimum matching" to be found. This can be used in instances where there are multiple quotes for a group of activities and each activity must be done by a different person, to find the minimum cost to complete all of the activities.

Steps

1. 1
Arrange your information in a matrix with the "people" on the left and the "activity" along the top, with the "cost" for each pair in the middle.
2. 2
Ensure that the matrix is square by the addition of dummy rows/columns if necessary. Conventionally, each element in the dummy row/column is the same as the largest number in the matrix.
3. 3
Reduce the rows by subtracting the minimum value of each row from that row.
4. 4
If there are columns without a zero, reduce the columns by subtracting the minimum value of each column from that column.
5. 5
Cover the zero elements with the minimum number of lines it is possible to cover them with. (If the number of lines is equal to the number of rows then go to step 9)
6. 6
Add the minimum uncovered element to every covered element. If an element is covered twice, add the minimum element to it twice.
7. 7
Subtract the minimum element from every element in the matrix.
8. 8
Cover the zero elements again. If the number of lines covering the zero elements is not equal to the number of rows, return to step 6.
9. 9
Select a matching by choosing a set of zeros so that each row or column has only one selected.
10. 10
Apply the matching to the original matrix, disregarding dummy rows. This shows who should do which activity, and adding the costs will give the total minimum cost.

Community Q&A

Search
• Question
How do the Dijkstra and Floyd algorithms differ?
You can use the Dijkstra algorithm to compute the shortest path from the source node to any other node. You can use the Floyd-Warshall algorithm to compute the shortest path from any node to any node. Don't use Dijkstra if there are arcs with negative weight. If there is a negative cycle in your graph, you cannot use a polynomial algorithm.
• Question
How is the Hungarian method applied for obtaining a solution if the matrix is a rectangle?
You would first add "dummy" row(s) or column(s) to make it square, with the "dummy" value being the highest value from that column or row, respectively.
• Question
Can the column reduction be done first and row reduction second?
Yes, it does not matter which reduction you do first. Doing row reduction first will give you a different final matrix, but the optimal solution obtained from that matrix will be the same as you get by doing the column reduction first. Furthermore, doing the row reduction first can sometimes reduce the number of steps required to get the optimal solution.
200 characters left

Tips

• If you wish to find a maximum matching rather than a minimum, multiply each number by -1 in step 1, then follow the steps as written.
⧼thumbs_response⧽
• A key insight here is that adding the same number to all entries in one row or column of the matrix produces a new matrix with the same optimal solution. This is what allows us to get away with the reduction of the matrix in step 6.
⧼thumbs_response⧽
Submit a Tip
All tip submissions are carefully reviewed before being published
Thanks for submitting a tip for review!

Things You'll Need

• Paper
• Pen/pencil
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://www.wikihow.com/Use-the-Hungarian-Algorithm", "fetch_time": 1685602711000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2023-23/segments/1685224647614.56/warc/CC-MAIN-20230601042457-20230601072457-00508.warc.gz", "warc_record_offset": 1138437938, "warc_record_length": 89280, "token_count": 753, "char_count": 3355, "score": 4.0, "int_score": 4, "crawl": "CC-MAIN-2023-23", "snapshot_type": "latest", "language": "en", "language_score": 0.8873178362846375, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00002-of-00064.parquet"}