# Hungarian method for non-integral edge weights?

 3 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 33●1●5 accept rate: 0%

 4 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. answered 10 Sep '12, 16:03 fbahr ♦ 4.6k●7●16 accept rate: 13% 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 ♦
 6 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 answered 09 Sep '12, 17:37 Nathan Brixius 212●2 accept rate: 0% Michael Trick ♦♦ 4.1k●5●16●33
 2 You can get rid of negative numbers by adding a constant to all costs. answered 10 Sep '12, 03:35 jfpuget 2.5k●3●10 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
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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: