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.
It still works when you take real valued weights, as long as you are careful. Such discussion is usually avoided because you need to be careful about what you mean by a real number and how you are representing it, plus the fact that you don't actually have the ability to use any real number as a weight. Because of these caveats, people tend to stick to rational numbers or integers, since the problem doesn't gain anything from going to the real numbers, as you can scale the weights by a large multiplicative factor to move them very far apart and then "round" to some close rational number. Since there are a finite number of numbers involved, there is infact guarenteed to be an $\alpha\in\mathbb{N}$ such that replacing $r_i$ with $\lceil\alpha r_i\rceil$ doesn't change the solution to the problem
The Hungarian algorithm (HA) still works efficiently for real weights; see Remark 3.2.12 on p.129 of West's "Introduction to Graph Theory", 2nd edn., for example. In brief, suppose we run the algorithm on a weighted $K_{n,n}$. Recall that the HA maintains a partial matching $M$ at each step; once that matching becomes full-size, the algorithm is done. The size of $M$ never decreases in any iteration of the HA, and each iteration that it does not strictly increase, the number of vertices in one partite set searched by the augmenting-path algorithm does increase, which means that $M$ has to get bigger at least once every $n$ iterations of the HA. So the HA terminates in at most $n^2$ steps. This argument is purely combinatorial and works just as well for real weights.
