Talk:Hungarian algorithm

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated C-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
C Class
Mid Importance
 Field:  Discrete mathematics

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)

This is an article on the Hungarian method, not a tutorial on Operations Research. The reader is assumed to have sufficient knowledge on the subject in order to understand what it is about. Terms such as 'matrix' and 'prime zeros' are no more copyrighted than 'algorithm', it's standard terminology on the topic, so I don't know what you're on about. Miskin 14:34, 24 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)

Actually I don't understand what you're talking about. To my knowledge there's no reference to any problems elsewhere. Again, you're asking a tutorial on optimization, which is beyong the scope of the article (for the obvious reasons). Miskin 14:34, 24 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)

Answering my question: the lines of the matrix stand for the first vertex set, and the columns stand for the second vertex set. Bender05 13:16, 24 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 (talk) 11:03, 17 May 2009 (UTC)

Aweful example, incomplete... —Preceding unsigned comment added by (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: —Preceding unsigned comment added by ArturDwornik (talkcontribs) 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 (talk) 00:01, 12 March 2012 (UTC)

Matrix Interpretation—Step 3[edit]

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? (talk) 07:55, 16 March 2014 (UTC)

n^3 time[edit]

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 (talk) 14:06, 27 April 2016 (UTC)