Talk:Hungarian algorithm

From Wikipedia, the free encyclopedia

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)