# Hungarian Algorithm with different metric

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?

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.