I had a problem where I need to apply bipartite weighted matching where the weights are real numbers(positive and negative). I have looked at several implementations of the "Hungarian method" but all of them expect the cost matrix of non-negative integers as input.

Moreover, I even looked at the pseudo code given in Figure 11-2 of Combinatorial Optimization: Algorithms and Complexity by Papadimitriou & Steiglitz. Even there, the pseudo code expects as input, cost matrix of non-negative integers. From what I understand of the algorithm, there shouldn't be any such restriction. Am I missing something here?

asked 09 Sep '12, 13:29

stressed_geek's gravatar image

stressed_geek
3315
accept rate: 0%

edited 09 Sep '12, 22:01


Yes, the Hungarian method for the assignment problem can be applied to matrices of non-negative real numbers – and although his seminal paper was only referring to integer instances, Kuhn apparently knew this all along.

For those who – unlike me – actually know what they are talking about: there's a variety of review papers discussing the story/rationale behind and feasibility of the generalization to real-valued coefficients [1,2,3]; the tl;dr version: Kőnig, Egerváry (who `put` the "Hungarian" in Kuhn's Hungarian method), Birkhoff, Edmonds, et al. – didn't dig much deeper than that.

link

answered 10 Sep '12, 16:03

fbahr's gravatar image

fbahr ♦
4.6k716
accept rate: 13%

edited 11 Sep '12, 14:18

2

cool. relates to the earlier rational rhs/cost discussion: for integrality, TU of the matrix and integrality of rhs is sufficient, and both are satisfied for the assignment problem, regardless of cost coefficients.

(11 Sep '12, 03:25) Marco Luebbecke ♦

The Hungarian algorithm is not the only way to go here. I like Jonker and Volgenant's code - the algorithm has better asymptotic complexity than the Hungarian method and their implementation is very efficient. Here is a Matlab port - the original C++ code is probably around if you look for it.

code

link

answered 09 Sep '12, 17:37

Nathan%20Brixius's gravatar image

Nathan Brixius
2122
accept rate: 0%

edited 09 Sep '12, 18:03

Michael%20Trick's gravatar image

Michael Trick ♦♦
4.1k41533

The Hungarian method relies on an integral duality theorem which is true for bipartite graphs and integer data, not for general graphs, not for rational data in general. If your data is rational you can still try to scale (multiply denominators by gcd). If you have negative edge weights, I believe [99% sure, but not 100%] that you can add the most negative weight to all edge weights so that the smallest is zero [this can be corrrected once you have a solution].

link

answered 09 Sep '12, 14:05

Marco%20Luebbecke's gravatar image

Marco Luebbecke ♦
3.4k1615
accept rate: 16%

edited 09 Sep '12, 14:08

1

I am sorry to cause confusion, but my edges weights are real numbers and not rational. Have updated the original post accordingly.

(09 Sep '12, 22:06) stressed_geek
2

nothing on a computer is real ;-) with floating point numbers (like "doubles") we always compute with a small subset of the rationals (unless you use rational arithmetic); "all" the digits of an irrational number would not fit into anybody's main memory... so, rational numbers are usually a good enough approximation. it is even known that several prominent algorithms (like the simplex method) are not finite on real/irrational input.

(10 Sep '12, 00:19) Marco Luebbecke ♦
2

Marco, do you have an example where the duality is not true for rational data (or even reals)?

(10 Sep '12, 07:22) Michael Trick ♦♦

@Mike, whenever the data is such that the determinant is fractional (binary vectors from adjcency matrix replaced in one column by RHS vector) the LP optimal solution could be fractional, then we have an integer duality.

To construct an example remains interesting, though (and, no, I do not have such an example)

(10 Sep '12, 09:54) Marco Luebbecke ♦

@Marco: Are you sure about this? As the technology matrix of the assignment problem is totally unimodular, its LPR should always results in integer optimum.

(10 Sep '12, 10:17) Ehsan ♦

@Ehsan, yes, 100% sure. TU of the matrix means, for computing the basic solution's coordinates, you divide by +/-1 in Cramer's rule. However, the numerator is a determinant which is computed from a matrix which contains the right hand side. So, for fractional RHS, you may have a fractional determinant.

TU is only helpful with integer data.

(10 Sep '12, 10:24) Marco Luebbecke ♦
1

@Marco: For the fractional RHS case, you're right. But here, @stressed_geek has asked about the case where objective function coefficients are fractional, not the RHS vector.

(10 Sep '12, 10:32) Ehsan ♦

I agree with Ehsan's comments. The RHS is all integer. Near as I can tell, the hungarian algorithm does not rely on integrality in costs for correctness.

(11 Sep '12, 11:36) Michael Trick ♦♦

@Michael @Ehsan me too; see my comment to @fbahr's answer.

(11 Sep '12, 11:54) Marco Luebbecke ♦
showing 5 of 9 show 4 more comments

You can get rid of negative numbers by adding a constant to all costs.

link

answered 10 Sep '12, 03:35

jfpuget's gravatar image

jfpuget
2.5k310
accept rate: 8%

thanks, @JF for removing my last percent of doubt ;-)

(10 Sep '12, 03:43) Marco Luebbecke ♦
3

It is even one of the basic step of the hungarian method! It basically work by adding and subtracting constant over lines and rows

(10 Sep '12, 04:32) jfpuget
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×231
×190
×28
×17

Asked: 09 Sep '12, 13:29

Seen: 3,474 times

Last updated: 11 Sep '12, 14:18

OR-Exchange! Your site for questions, answers, and announcements about operations research.