1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The algorithms still work properly, provided you have a reasonable computational model of what a 'real number' is. See Section 1.4 of Lovász' book An Algorithmic Theory of Numbers, Graphs and Convexity. $\endgroup$ – Tony Huynh Nov 9 '15 at 14:26
  • $\begingroup$ If I answered your question, you should consider accepting it $\endgroup$ – Stella Biderman Jan 24 '16 at 16:13
  • $\begingroup$ @TonyHuynh: Thank you very much for the reference! Thanks to it I could better understand Stella's answer. And please forgive me for the late reply. $\endgroup$ – Khue Jan 25 '16 at 14:05
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thanks for your answer. And please forgive me for the late reply (I completely forgot this question). I think some methods only work for integers (and not because the problem doesn't gain anything from going to the real numbers). For example this one: jorlin.scripts.mit.edu/docs/publications/38-ScalingSimplex.pdf Do you have any comments on that? $\endgroup$ – Khue Jan 25 '16 at 14:04
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.