The cost function in the Weighted Bipartite Matching Problem (a.k.a the Assignment Problem)

119 Views Asked by At

In the definition of this problem, the weight/cost function generally takes value in $\mathbb{Z}$ (or sometimes $\mathbb{Q}$). This is what I observed from some books (e.g. "Combinatorial Optimization: Polyhedra and Efficiency" by Alexander Schrijver) and some implementations I found on the web.

My question is: How does a real-valued cost function affect the solution, such as the Hungarian method?

Thank you in advance.

1

There are 1 best solutions below

0
On

As far as I know, having a real valued cost function shouldn't change anything.

By the way, one simple and efficient way to solve this problem is via linear programming, as follows. Define a variable $x_e$ for each edge in the graph, and maximize $\sum_e{w(e)x_e}$ subject to $x_e \geq 0$ for all $e \in E$ and $\sum_{e:v \in e}{x_e} \leq 1$ for every vertex $v \in V$.

The reason this works is that the vertices of the polytope defined by the inequalities correspond to perfect matchings (this is Birkhoff's theorem), so you will always get 0-1 solutions.