1
$\begingroup$

I have a modified Assignment Problem, that can almost be solved using the Hungarian Algorithm.

Instead of trying to minimize the sum of costs of assignments, I want to minimize the cost of the costliest assignment. Using the explanation of Hungarian algorithm at wikipedia , one could say that I want to find a solution that minimizes the amount paid to the highest salaried worker.

One suggestion I've received is to simply use a modified cost matrix, with every value in the cost matrix raised to a biggish exponent (say, 10), and then use the standard Hungarian Algorithm.

But perhaps there is a better way?

$\endgroup$
1
$\begingroup$

The suggestion is good, as $$ \lim_{p \rightarrow \infty} \left( |x_1|^p + \cdots |x_n|^p \right)^{1/p} = \max |x_i| $$

I can see a pretty good greedy algorithm that may do it. First, define $M$ as the sum of all current costs. Successively delete the highest cost individual assignment (by replacing that cost with $M$) as long as there is any feasible assignment, where the word "feasible" now means "cost below $M$." No matter what happens, you can delete at least $(n-1)$ boxes. Let's see, if, at any stage, you get a feasible solution that does not use the highest remaining cost, clearly you can delete that one without disturbing anything. So then you get to delete a second box for free.

$\endgroup$
  • $\begingroup$ Thank you for the answer. What if the N highest cost assignments are all for the same row? Wouldn't your algorithm delete all but one of them, and then get stuck? Since at that point deleting the highest cost assignment leads to a non-feasible solution? $\endgroup$ – avl_sweden Apr 12 '13 at 6:43
  • $\begingroup$ @avl_sweden, yes. In that case, since we must use one box (assignment) in each column and one in each row, you have an easy answer. Instead of being stuck, you know that the remaining high cost in that row must be used, and you do not even care what happens in the other rows. Put another way: keep deleting highest cost boxes, one at a time, until there is no feasible solution. Then return the last deleted to its original value, so you have the final feasible solution. $\endgroup$ – Will Jagy Apr 12 '13 at 18:07

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.