<p>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 <a href="http://en.wikipedia.org/wiki/Hungarian_algorithm" rel="nofollow">Hungarian method</a> but all of them expect a cost matrix of non-negative integers as input.</p>

<p>Moreover, I even looked at the pseudo code given in Figure 11-2 of <a href="http://rads.stackoverflow.com/amzn/click/0486402584" rel="nofollow">Combinatorial Optimization: Algorithms and Complexity by Papadimitriou &amp; Steiglitz</a>. 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?</p>

CC BY-SA 3.0
2012-09-09T19:26:34.463Z
You seem to be asking two questions here: one about non-negative rationals weights and one about rational weights. Can you clarify this?
Tyson Williams
CC BY-SA 3.0
2012-09-09T20:33:21.640Z
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.
Peter Shor 
CC BY-SA 3.0
2012-09-10T00:17:07.323Z
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.
Peter Shor 
CC BY-SA 3.0
2012-09-10T02:09:29.763Z
I am sorry to cause confusion, but the edges weights in my case are real numbers and not rational. Have updated the original post accordingly.
stressed_geek
CC BY-SA 3.0
2012-09-10T03:33:09.207Z
@TysonWilliams I am asking about real valued weights. The problem regarding non-negative weights can be avoided using solution pointed by Peter Shor in his comment.
stressed_geek
CC BY-SA 3.0
2012-09-10T14:18:59.533Z
My guess is that everyone assumes non-negative integers for simplicity of presentation. For non-negative reals, I would expect that sufficiently good rational approximations will work.
Tyson Williams
CC BY-SA 3.0
2012-09-10T17:11:17.793Z
@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?
Peter Shor 
CC BY-SA 3.0
2012-09-10T18:13:13.107Z
In fact, this question seems to prejudge by answering affirmatively to Peter's first question. so I'd ask @stressed_geek: do you have any example where you need so much precision that the algorithm breaks ?
Suresh Venkat
CC BY-SA 3.0
2012-09-11T01:48:55.673Z
@PeterShor Of course.  I was just trying to provide some intuition on why non-negative reals shouldn't be much different theoretically from non-negative integers for this application.
Tyson Williams
CC BY-SA 3.0
2012-09-14T11:29:38.027Z
@PeterShor and others: The straight-forward implementation of Hungarian method seems to work fine by naively modifying it to use floating-point arithmetic. Thanks!
stressed_geek
<graph-theory><co.combinatorics><graph-algorithms><optimization><linear-programming>
Can the Hungarian method be used with real edge weights?
stressed_geek
# Can the Hungarian method be used with real edge weights?

(Asked by: username_0 on 2012-09-09)

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](http://en.wikipedia.org/wiki/Hungarian_algorithm) 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](http://rads.stackoverflow.com/amzn/click/0486402584). 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?

**Tags:** graph-theory, co.combinatorics, graph-algorithms, optimization, linear-programming

> **Comments:**
> **username_1**: You seem to be asking two questions here: one about non-negative rationals weights and one about rational weights. Can you clarify this?  
> **username_2**: 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.  
> **username_2**: 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.  
> **username_0**: I am sorry to cause confusion, but the edges weights in my case are real numbers and not rational. Have updated the original post accordingly.  
> **username_0**: @TysonWilliams I am asking about real valued weights. The problem regarding non-negative weights can be avoided using solution pointed by username_2in his comment.  
> **username_1**: My guess is that everyone assumes non-negative integers for simplicity of presentation. For non-negative reals, I would expect that sufficiently good rational approximations will work.  
> **username_2**: @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?  
> **username_3**: In fact, this question seems to prejudge by answering affirmatively to Peter's first question. so I'd ask @username_0: do you have any example where you need so much precision that the algorithm breaks ?  
> **username_1**: @PeterShor Of course.  I was just trying to provide some intuition on why non-negative reals shouldn't be much different theoretically from non-negative integers for this application.  
> **username_0**: @PeterShor and others: The straight-forward implementation of Hungarian method seems to work fine by naively modifying it to use floating-point arithmetic. Thanks!  

---

## 0 answers

