This is the
talk page for discussing improvements to the
Hungarian algorithm article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
This
level-5 vital article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
The title of the "Theory" section is not quite right. I can't see that it is any more theoretical than other sections. What it does is that it decsribes the algorithm. Unfortunately the description is not self-contained, and thus completely unreachable for non-specialist. Actually the terse formulation and references to concepts not introduced (the matrix, prime zeros, etc) make me think that this is a violation of copyright (a paragraph taken from some larger work) Wazow 17:44, 4 March 2006 (UTC)
The article should describe the problem solved by the algorithm briefly (not only refer to the problem description elswhere). It is impossible to describe the solution well, if the key objects in the problem are not defined in the text. Wazow 17:45, 4 March 2006 (UTC)
Macrakis' removal of the algorithm section (which I didn't notice) did make the article largely uncomprehensible. Still, the rest of what you said (about copyrighted terminology, not enough background theory etc) remain irrational. Miskin 14:53, 24 March 2006 (UTC)
I am not sure on which matrix exactly we are supposed to work. Suppose I want to find a matching of maximum weight in a weighted bipartite graph; shall I use the algorithm directly on the adjacency matrix of that graph? Or do I have to build a matrix whose rows are attached to the first vertex set V1, whose columns are attached to the second vertex set V2, and whose entries contain the weight of edges from V1 to V2 (this would therefore be a submatrix of the adjacency matrix)? Bender05 10:29, 21 March 2006 (UTC)
This is already described in the modeling section although the answer should be straight-forward to someone who has a good understanding of the algorithm. It works on a matrix which can be modelized as a bi-partite graph and vice versa. By default, each k(i,j) entry on the matrix has the value of the flow of the equivalent arc a(i,j) (that is the arc joining the nodes i and j). The absence of an arc is equivalent to the presence of an arc of zero flow, hence the value in the matrix will be zero. The point of the Hungarian method is that you don't need to bother yourself with flow-networks. There's a technique to spot the "independent" zeros on the fly. Each state can be theoretically modeled on a bi-partite graph, but this requires the use of an extra algorithm (usually Ford and Fulkerson). This expansion of the algorithm is called Primal-Dual. Miskin 14:34, 24 March 2006 (UTC)
Moderators: can't you add some mathematical abilities to wiki so this scientific stuff can be done properly? Egnever 15:42, 24 March 2007 (UTC)
I removed Gaussian elimination and the references to Gaussian elimination because Gaussian elimination is not used in this algorithm. I am going to remove the reference from primed to the article Matrix (Mathematics) because the word primed does not appear in that article.
The modeling section could benefit from rewriting. How does one subtract a value from an infinite value yet retain in some way its relative value? Also, what does one do in the case of i workers and j jobs, when i does not equal j? If these things were explained or elaborated upon the section would be more useful.
The algorithm section could also benefit from rewriting. The term starred zero is undefined. I suspect that it is a reference to the algorithm as originally published, but it has no meaning in its current context. The algorithm section is incomplete without a description of how to produce more zeros in the matrix. The method is NOT Gaussian elimination. I could not find any meaning for I/O capacity equal to 1 or to independent zeros. In the context of Wikipedia, these have no meaning.
I found the sections titled Bipartite Graph Representation and A Minimization Problem to be self-contained (with their references) and useful, and appreciate these contributions. Aostrander ( talk) 22:31, 24 March 2008 (UTC)
It might be worth noting that Kuhn credits Jacobi with having essentially invented the algorithm a century earlier, though the connection wasn't realized until recently. -- Delirium ( talk) 04:51, 13 August 2008 (UTC)
In the section "The algorithm in terms of bipartite graphs", the argument for Delta being positive is unsatisfactory. While it is clear, that there is no edge from Z cup S to T\Z, it is not at all clear that there is no edge in the other direction. —Preceding unsigned comment added by 129.67.168.205 ( talk) 11:03, 17 May 2009 (UTC)
Aweful example, incomplete... —Preceding unsigned comment added by 84.226.159.223 ( talk) 13:45, 3 September 2009 (UTC)
The "Matrix interpretation" Section needs to be rewriten. Gready implementation of step 3 does not work in every case ! well writen O(n^3) description: http://csclab.murraystate.edu/bob.pilgrim/445/munkres.html —Preceding unsigned comment added by ArturDwornik ( talk • contribs) 18:29, 1 February 2010 (UTC)
Hi; I'm not sure that I've interpreted the description of the matrix implementation correctly- when I try this on the matrix [3,0,1;0,2,0;3,1,3], Step 1 reduces the bottom row by 1, but all of the other steps leave the matrix unchanged, right? As I have it, these are the other effects: Step 2: each column is decreased by zero. Step 3: Zeros are chosen ([middle-left or middle-right] and [top-centre or bottom-centre]), which means the only row without an assignment is either the top or the bottom, so I mark the centre column and thus whichever of the top/bottom rows I didn't already mark. So the only two unmarked values are the zeros in the middle row. Step 4: I subtract zero from each of the zeros in the middle row and add zero to the zeros in the centre column. When I repeat to Step 1, each row has a zero minimum so that's stopped helping too. — Preceding unsigned comment added by 71.79.250.78 ( talk) 00:01, 12 March 2012 (UTC)
I don't think the example does the problem justice, because you could just take the row wise argmin to get the solution. Yes the Hungarian Algorithm could be used here, but it doesn't explain the specific combinatorial optimization benefit — Preceding unsigned comment added by 193.174.55.143 ( talk) 12:38, 2 March 2022 (UTC)
Am I the only one who feels that textual references to rows and columns correspond to columns and rows in the diagrams? That is: we are reading rows when we mean columns, and vice versa. We are directed to 'Mark all rows having no assignments (row 1),' but isn't it column 1 that lacks a clear—ie, unambiguous—assignment, due to its containing two zeros?
I could easily be mistaken about this, because it's a long time since I learned the Hungarian Method. I'll see how things look after a review of my old notes! Aboctok ( talk) 21:32, 20 May 2011 (UTC)
I don't know if this is the cause of my confusion, but I too am confused by step 3. What does it mean to "first assign as many tasks as possible" How are we to do this? Isn't this equivalent to performing step 3?
75.82.11.172 (
talk)
07:55, 16 March 2014 (UTC)
I feel that the algorithm as presented is incorrect. Suppose we try to perform it on the following matrix:
Then we first mark row 3, then column 1, then row 1. Then we end up drawing two lines: through row 2 and column 1. This clearly does not cover all of the zeros. — Preceding unsigned comment added by Batconjurer ( talk • contribs) 12:00, 12 February 2018 (UTC)
No, just keep going: Row 3 -> Col 1 -> Row 1 -> Col 2 -> Row 2 -> Col 3 so you will draw a line through the three columns. -- 129.97.124.120 ( talk) 20:49, 8 October 2019 (UTC)
Page says "however Edmonds and Karp, and independently Tomizawa noticed that it can be modified to achieve an O(n^3) running time." Is there a citation for this? — Preceding unsigned comment added by 87.212.207.8 ( talk) 14:06, 27 April 2016 (UTC)
I have not found citations, but I think I have found a variation on the bipartite graph algorithm that runs in O(n^3) time.
I post it here first for some checking because I am not yet sure enough to modify the main article.
The algorithm still uses potentials as in the main article, but speeds up the modification of potential between matchings.
Define the weight of an edge in G as w(u,v)=c(u,v)-y(u)-y(v), the amount that the potential of that edge can be increased.
I think this is correct and has complexity O(n^3)
1. Potential property still holds: Suppose we have a matched edge (v,u) with v in T and u in S. Then d_v=d_u because (v,u) is the only edge entering u and has weight 0 (because it is tight). then the new y(u)+y(v) becomes y(u)+y(v)-d_u+d_v=y(u)+y(v)=c(u,v) Suppose we have an unmatched edge (u,v) with u in S and v in T. Then d_v ≤ d_u + w(u,v) therefore the new y(u)+y(v) becomes y(u)+y(v)-d_u+d_v≤y(u)+y(v)-d_u+d_u+w(u,v)=y(u)+y(v)+w(u,v)=c(u,v) This covers both proofs in the wikipedia article
2. Each round a new match is made: The path to the start from t described by the p_i's is the shortest path. The following statements are when going forward (from some unmatched s in S to some unmatched t in T) Let (u,v) be an edge on this path from S to T. Then d_v = d_u + w(u,v) because otherwise the path would have been shorter. And thus the new potential becomes tight: y(u)+y(v)+w(u,v) = c(u,v) Let (v,u) be an edge on this path from T to S. Then d_v = d_u because it was already tight, the potential doesn't change -> still tight All edges on our path are now tight and form an augmenting path, we get a new match.
Spaanse aak ( talk) 19:25, 19 March 2020 (UTC)
Hello fellow Wikipedians,
I have just modified one external link on Hungarian algorithm. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.
This message was posted before February 2018.
After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than
regular verification using the archive tool instructions below. Editors
have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the
RfC before doing mass systematic removals. This message is updated dynamically through the template {{
source check}}
(last update: 5 June 2024).
Cheers.— InternetArchiveBot ( Report bug) 20:45, 8 November 2017 (UTC)
The algorighm in step 3 is not true to all of the matrixes. — Preceding unsigned comment added by 132.70.66.14 ( talk) 13:18, 19 December 2017 (UTC)
Indeed: here's a small example (maybe smaller exist):
This will assign rows 1, 3, 4 and 5. Then it will mark: row 2 -> col 5 -> row (1 & 3) -> col (2 & 3) -> row (4 & 5) -> col (1 & 4) so that now everything is marked and 5 (vertical) lines are drawn. Yet, 4 lines are sufficient: col 5 and rows 3, 4 and 5. -- 129.97.124.120 ( talk) 20:55, 8 October 2019 (UTC)
Section The_algorithm_in_terms_of_bipartite_graphs says: (Precondition P:) "If {\displaystyle R_{T}\cap Z}R_T \cap Z is empty, then let " [...] (Note N:) "(note that the number of tight edges does not necessarily increase)."
I can't believe that this Note N holds under Precondition P. Also, the section "Proof that the algorithm makes progress" below says:
"that is, to either increase the number of matched edges, or tighten at least one edge"
I understand the "tighten at least one edge"-Part as exactly the Precondition-P-part from above !? (Also I assume the "increase the number of matched edges" probably relates to "If {\displaystyle R_{T}\cap Z}R_T \cap Z is nonempty..." from above?)
As you can infer, I am missing some connections... the "If {\displaystyle R_{T}\cap Z}R_T \cap Z is nonempty"-Part should be labeled something like "augmenting case", so that it could be related better to that mentioned corresponding part in the proof; or Z could be introduced as something like "the set of nodes that could possibly participate in an augmentation path", with relation to Berge's Lemma, to help unterstanding the purpose of Z from the start on. Fjf2002 ( talk) 19:26, 14 March 2021 (UTC)
It is unclear to me how to prove that step 5 of the matrix interpretation makes progress, considering that it does not appear to be equivalent to the potential adjustment in the bipartite graph interpretation. B52481 ( talk) 00:31, 14 May 2023 (UTC)
In step 3 it says "Repeat this till a closed loop is obtained." What is meant by loop? We just have a matrix with zero and nonzero elements. (I know a different algorithm where you have to "cover" all 0 by selecting a minimum number of rows and/or columns. You proceed by adding that row/col that removes a max. number of zeros not covered yet.) — MFH: Talk 15:03, 18 January 2024 (UTC)