Computing desk
< January 6	<< Dec \| January \| Feb >>	Current desk >

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 7[edit]

Hungarian algorithm: assignment step[edit]

... multiple rows ...
4 4 4 6 0 0 0 6 6 6 6 6 4 2 2 2 2 2
4 4 4 6 0 0 0 6 6 6 6 6 4 2 2 2 2 2
4 4 4 6 0 0 0 6 6 6 6 6 4 2 2 2 2 2
4 4 4 6 0 0 0 6 6 6 6 6 4 2 2 2 2 2
4 4 4 6 0 0 0 6 6 6 6 6 4 2 2 2 2 2

In various steps in the hungarian algorithm, one tries to assign rows to columns uniquely such that each (row, column) assignment has a 0. But this seems like a worst-case O(n!) problem, and it isn't explained how that would be done. Theoretically the article states that the hungarian algorithm is O(n^3)

Recently my code tried to process the above grid, but the O(n!) solution was so slow it caused a timeout. (There's no solution in the above grid and it's relatively hard to detect creating a worst case scenario.) AltoStev (talk) 01:32, 7 January 2023 (UTC)[reply]

I don't know which description of the algorithm you are following, but when implemented correctly, it should take only

O(n^{4})

steps, even if it is the original version. Following the procedure described in Hungarian algorithm § Matrix interpretation, Step 2, you should subtract, for each column, its minimum element from all elements in that column. If all rows are equal, the result is a zero matrix, meaning that any and all assignments are optimal. I hope this helps.

I must confess that I find both descriptions of the algorithm in our article impossible to follow. The description in terms of bipartite graphs mixes the algorithmic steps with their justification, which is confusing. The algorithm is complicated enough; clarity will be served by separating its justification from its description. Is it the case that the correspondence between

\textstyle {G_{y}^{\to }}

and

M

is an invariant, so that one of the two is superfluous? It also mixes a command mode, addressing a computing servant in the second person, with the first-person pluralis modestiae. So who is supposed to be executing the steps, the computer or "us"? The description in terms of a matrix mixes the algorithmic steps in a confusing way with their application to examples, or even only describes them by such applications.

--Lambiam 19:04, 7 January 2023 (UTC)[reply]

Sorry, should've clarified. Subtracting from columns doesn't work since the actual grid was

0 0 0 0 6 6 6 0 0 0 0 0 0 0 0 0 0 0 <-- all columns have zeroes (1)
0 0 0 0 6 6 6 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 6 6 6 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 6 6 6 0 0 0 0 0 0 0 0 0 0 0
2 2 2 0 6 6 6 2 2 2 2 2 2 0 0 0 0 0
0 0 0 0 6 6 6 0 0 0 0 0 0 0 0 0 0 0
2 2 2 0 6 6 6 2 2 2 2 2 2 0 0 0 0 0
2 2 2 0 6 6 6 2 2 2 2 2 2 0 0 0 0 0
4 4 4 6 0 0 0 6 6 6 6 6 4 2 2 2 2 2 <-- all columns have zeroes (2)
4 4 4 6 0 0 0 6 6 6 6 6 4 2 2 2 2 2
4 4 4 6 0 0 0 6 6 6 6 6 4 2 2 2 2 2
4 4 4 6 0 0 0 6 6 6 6 6 4 2 2 2 2 2
4 4 4 6 0 0 0 6 6 6 6 6 4 2 2 2 2 2

Meaning that every column has a minimum of 0

And yes, I was following the matrix algorithm. I also find this nice visual explanation: https://medium.com/@riya.tendulkar/the-assignment-problem-using-hungarian-algorithm-4f105729af18 but that doesn't show the part about selecting the zeroes either.

AltoStev (talk) 21:58, 7 January 2023 (UTC)[reply]

The best description I've found thus far is here. It is still a tough read, but it gives me the impression I could write a program based on the pseudocode description. Also, here is an implementation in Python. I have not verified that it is correct, and also not looked at its complexity --Lambiam 17:47, 8 January 2023 (UTC)[reply]

Thanks for the links, after wrangling with descriptions of the algorithm I think I understand now, which resolves my question. AltoStev (talk) 00:41, 12 January 2023 (UTC)[reply]