I had a problem where I need to apply bipartite weighted matching on a graph where the edge weights are real (positive and negative). I have looked at several implementations of the Hungarian method but all of them expect a 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?

  • 1
    $\begingroup$ You seem to be asking two questions here: one about non-negative rationals weights and one about rational weights. Can you clarify this? $\endgroup$ – Tyson Williams Sep 9 '12 at 19:26
  • 4
    $\begingroup$ The difference between non-negative and negative weights is fairly easy to handle: just add a fixed constant to all the edges to make the weights positive. (Although it might depend on whether for your application, you would rather include an edge with negative weight or no edge at all.) Since an assignment always has $n$ edges, the optimal assignment is the same before and after this addition. $\endgroup$ – Peter Shor Sep 9 '12 at 20:33
  • 6
    $\begingroup$ I have no idea why all the implementations you looked at take integers as inputs. The algorithm itself is strongly polynomial, so theoretically it should work fine with real numbers. Maybe something goes wrong when you try to implement it with floating point arithmetic because of round-off error. There should be ways of fixing that, but it seems possible the straightforward implementation doesn't work right. $\endgroup$ – Peter Shor Sep 10 '12 at 0:17
  • 2
    $\begingroup$ @Tyson: for a actual application, you really don't want to use rational approximations. You want to use floating-point numbers if you can. So the question is: if you program the Hungarian algorithm naively using floating-point arithmetic, does anything go wrong? If it does, what's the best way to fix it? $\endgroup$ – Peter Shor Sep 10 '12 at 17:11
  • 2
    $\begingroup$ @PeterShor and others: The straight-forward implementation of Hungarian method seems to work fine by naively modifying it to use floating-point arithmetic. Thanks! $\endgroup$ – stressed_geek Sep 14 '12 at 11:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.