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?
 A: 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.
A: Actually, this change of metric makes the problem a little easier to compute. You can find the objective value by dichotomy. To answer the question "is it possible to find a matching whose highest edge costs $M$ ?", you just remove the edges costing more than $M$ and search for a perfect matching (which is easier than the minimum-cost matching).
This simple idea, with a Hopcroft-Karp algorithm, already gives a $O(|E| \sqrt{|V|} \log(|E|))$ algorithm ; but actually you could make it run faster, because the subgraphs are included one in the other so you can reuse the information from one to the other. If I remember correctly, you can completely remove the $\log(n)$ factor by doing it in the right order ; but I'm not sure about it.
