Hungarian algorithm: Revision history

14 May 2023

• curprev 02:4302:43, 14 May 2023 B52481 talk contribs 36,336 bytes +138 add more about the time complexity in →Adding the j-th job in O(jW) time undo
• curprev 02:4002:40, 14 May 2023 B52481 talk contribs m 36,198 bytes +196 minor improvements to →Adding the j-th job in O(jW) time undo
• curprev 02:3402:34, 14 May 2023 B52481 talk contribs m 36,002 bytes −44 remove math from headings undo
• curprev 02:3102:31, 14 May 2023 B52481 talk contribs 36,046 bytes +7,192 add O(n^3) Hungarian algorithm + code undo Tag: Visual edit: Switched
• curprev 00:3100:31, 14 May 2023 B52481 talk contribs 28,854 bytes +23 mark last step of matrix interpretation as unclear undo Tag: Visual edit: Switched

20 April 2023

• curprev 15:4615:46, 20 April 2023 Cadduk talk contribs 28,831 bytes −180 Undid revision 1144784037 by Cmglee (talk) The procedure does not use the same naming conventions as the rest of the article. The presented algorithm seems to not work every time, or the description is at least not complete (what if no row or column has a single 0 ?), this is not the one detailed in the article. It is very confusing without a detailed explanation of the steps. undo Tag: Undo

16 March 2023

• curprev 03:1703:17, 16 March 2023 Cmglee talk contribs 29,011 bytes +317 →Example: Add exhaustive proof undo

15 March 2023

• curprev 15:2415:24, 15 March 2023 Cmglee talk contribs 28,694 bytes +28 →Example: Use less contrived values undo
• curprev 15:1115:11, 15 March 2023 Cmglee talk contribs 28,666 bytes +52 →Example: Add {{diagonal split header}} undo
• curprev 15:1015:10, 15 March 2023 Cmglee talk contribs 28,614 bytes +180 →top: Add worked example diagram undo Tag: Reverted

28 February 2023

• curprev 15:2415:24, 28 February 2023 12.187.176.10 talk 28,434 bytes +9 →Bipartite graph formulation undo
• curprev 15:2415:24, 28 February 2023 12.187.176.10 talk 28,425 bytes +10 →Bipartite graph formulation: , edited to make definition of E explicit undo

30 January 2023

• curprev 07:0707:07, 30 January 2023 OAbot talk contribs m 28,415 bytes +16 Open access bot: doi added to citation with #oabot. undo

11 January 2023

• curprev 23:3623:36, 11 January 2023 AltoStev talk contribs 28,399 bytes −38 Changing short description from "Combinatorial optimization algorithm that solves the assignment problem in polynomial time" to "Polynomial-time algorithm for the assignment problem" undo Tag: Shortdesc helper
• curprev 23:3523:35, 11 January 2023 AltoStev talk contribs 28,437 bytes +827 →Matrix interpretation: Revise section. The logical structure is clearer but I use GOTO and (Else branch continued) in Step 4 so that could probably be simplified somehow. undo Tag: 2017 wikitext editor

8 January 2023

• curprev 22:1422:14, 8 January 2023 Joriki talk contribs 27,610 bytes +40 →Matrix formulation: removed unnecessary double permutation (due to the cyclic invariance of the trace, the two permutations can be combined into one – only the workers or the jobs need to be permuted, not both) undo

31 December 2022

• curprev 19:0119:01, 31 December 2022 AltoStev talk contribs 27,570 bytes −23 →Step 4: make clear that value is uncovered (based on https://medium.com/@riya.tendulkar/the-assignment-problem-using-hungarian-algorithm-4f105729af18) undo Tag: 2017 wikitext editor

28 October 2022

• curprev 07:4007:40, 28 October 2022 128.179.254.166 talk 27,593 bytes 0 →Step 4: Replace "crossed" with "covered" for clarity ("crossed" was not used before and one can wonder if it means something new). undo

1 October 2022

• curprev 21:5521:55, 1 October 2022 PlasticStylus talk contribs 27,593 bytes +52 →External links: Changed link to point to a Research Gate copy of the course notes. undo Tag: Visual edit

29 September 2022

• curprev 09:2309:23, 29 September 2022 136.36.225.23 talk 27,541 bytes 0 →Step 2: task 1 is done efficiently by agent a, but the issue in the assignment implied by this matrix seems to be between agents c and d (since it isn't apparent that they are fit for any other tasks) undo Tags: Mobile edit Mobile web edit
• curprev 09:1709:17, 29 September 2022 136.36.225.23 talk 27,541 bytes +7 →Bipartite graph formulation: which is "easier" is a matter of taste. undo Tags: Mobile edit Mobile web edit

29 August 2022

• curprev 00:5900:59, 29 August 2022 Leopd talk contribs 27,534 bytes −275 →Matrix interpretation: Removing confusing tag as the key issue has been addressed in that the matrix interpretation has been clearly described. Also this explanation is vastly clearer than the bipartite graph version. undo Tags: Mobile edit Mobile web edit

27 July 2022

• curprev 21:5721:57, 27 July 2022 2620:15c:53:200:2f56:eef7:385c:f879 talk 27,809 bytes −219 Remove a broken link. undo Tag: Visual edit

12 July 2022

• curprev 14:2714:27, 12 July 2022 Cadduk talk contribs 28,028 bytes 0 change line for row and column undo

30 May 2022

• curprev 19:3819:38, 30 May 2022 Evan Shimoniak talk contribs m 28,028 bytes +27 Added link to matrix trace undo

3 April 2022

• curprev 16:5516:55, 3 April 2022 Cadduk talk contribs 28,001 bytes +2,680 Correction of the Step 3, also switched to a better example undo

7 March 2022

• curprev 17:2117:21, 7 March 2022 206.12.139.49 talk 25,321 bytes −24 Fixed link undo

6 March 2022

• curprev 23:4323:43, 6 March 2022 128.189.241.136 talk 25,345 bytes +139 Added Julia implementation undo

4 February 2022

• curprev 23:3423:34, 4 February 2022 Jonesey95 talk contribs 25,206 bytes −2 Changing short description from "a combinatorial optimization algorithm that solves the assignment problem in polynomial time" to "Combinatorial optimization algorithm that solves the assignment problem in polynomial time" (Shortdesc helper) undo

13 January 2022

• curprev 23:3423:34, 13 January 2022 Jarble talk contribs 25,208 bytes +115 adding a short description undo

15 November 2021

• curprev 07:2107:21, 15 November 2021 Cedar101 talk contribs m 25,093 bytes 0 →Step 3: split subsection undo
• curprev 07:1907:19, 15 November 2021 Cedar101 talk contribs m 25,093 bytes −24 Δ undo
• curprev 07:1507:15, 15 November 2021 Cedar101 talk contribs 25,117 bytes −371 split subsections, {{mvar}} undo
• curprev 07:1007:10, 15 November 2021 Citation bot talk contribs 25,488 bytes +154 Alter: url. URLs might have been anonymized. Add: title, archive-date, archive-url. Changed bare reference to CS1/2. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_toolbar undo

17 October 2021

• curprev 21:3721:37, 17 October 2021 PlasticStylus talk contribs 25,334 bytes +5 →Matrix interpretation: Added a single word "then" to Step 3, to clarify that one zero gets assigned, before the second one gets crossed out. undo Tag: Visual edit
• curprev 08:0308:03, 17 October 2021 Citation bot talk contribs 25,329 bytes +29 Add: s2cid. | Use this bot. Report bugs. | Suggested by BrownHairedGirl | Linked from User:BrownHairedGirl/Articles_with_bare_links | #UCB_webform_linked 821/2197 undo

15 October 2021

• curprev 05:0905:09, 15 October 2021 143.248.151.61 talk 25,300 bytes 0 max changed to min. In case of an NxM matrix, the maximum number of matchings (n) is min(number of people, number of assignments) undo

11 July 2021

• curprev 15:0115:01, 11 July 2021 BernardoSulzbach talk contribs m 25,300 bytes −2 →Matrix interpretation: rm vestigial line break undo

24 June 2021

• curprev 12:5212:52, 24 June 2021 Slamket talk contribs 25,302 bytes 0 Cost $9 for 'Dave' for 'Sweeping Floors' was incorrect based on the result being $6. undo Tag: Manual revert
• curprev 07:3207:32, 24 June 2021 203.69.151.88 talk 25,302 bytes 0 →Example undo Tag: Reverted

4 May 2021

• curprev 01:4701:47, 4 May 2021 FrescoBot talk contribs m 25,302 bytes −84 Bot: link syntax and minor changes undo

19 March 2021

• curprev 08:1908:19, 19 March 2021 WikiCleanerBot talk contribs m 25,386 bytes −3 v2.04b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation - Empty list item) undo Tag: WPCleaner

16 March 2021

• curprev 12:2312:23, 16 March 2021 Dr.Saxena talk contribs m 25,389 bytes +953 →Matrix interpretation undo Tag: use of deprecated (unreliable) source

14 March 2021

• curprev 18:5518:55, 14 March 2021 Fjf2002 talk contribs m 24,436 bytes −3 Grammar corrected undo

10 February 2021

• curprev 09:2309:23, 10 February 2021 203.97.16.73 talk 24,439 bytes +2,609 →The algorithm in terms of bipartite graphs: Prove that the algorithm always makes progress when the matching is not yet of maximum possible size. undo

24 December 2020

• curprev 19:0519:05, 24 December 2020 84.245.121.46 talk 21,830 bytes +10 →lede: names in ref undo

12 December 2020

• curprev 13:2713:27, 12 December 2020 Erkinalp9035 talk contribs 21,820 bytes −1 No edit summary undo Tag: 2017 wikitext editor
• curprev 13:2613:26, 12 December 2020 Erkinalp9035 talk contribs 21,821 bytes +38 No edit summary undo Tag: 2017 wikitext editor

10 December 2020

• curprev 02:3902:39, 10 December 2020 Bender the Bot talk contribs m 21,783 bytes +1 →top: HTTP → HTTPS for Wayback Machine, replaced: http://web.archive.org/ → https://web.archive.org/ undo Tag: AWB

7 December 2020

• curprev 15:2115:21, 7 December 2020 Zgebiit talk contribs m 21,782 bytes +42 Fix broken link undo