Minimizing maximum cost in an one-to-one assignment problem

Question

I want to compute a one-to-one assignment, from A to B where A and B have n elements. Each element of A will be assigned to one element in B. There is an associated cost between each element of A and B. The goal is to minimize the maximum cost of the assignment.

How to compute such an assignment using the cost matrix? I need to select an element from each row/column such that minimax strategy is achieved.

I was able to achieve this by listing all possible assignments and calculating their maximum costs and then selecting the one with the least maximum cost, but I wonder if there's a better approach.

Answer 1

The easiest is probably as a MIP (Mixed-Integer Programming) model:

 min z
 z >= c[i,j]*x[i,j]   ∀ i,j
 sum(i, x[i,j]) = 1   ∀ j
 sum(j, x[i,j]) = 1   ∀ i
 x[i,j] ∈ {0,1}

This can be solved with any MIP solver.

Answer 2

A brute force polynomial cost algorithm based on repeated application of max matching in bipartite graph:

Order the pairs by assignment cost. Take n cheapest pairs. This determines a bipartite graph with A and B as vertices (pairs are edges). Try to find a matching in this graph. If found, it determines the optimal one-to-one assignment.

If not found, add the next pair. Repeat until a matching is found.

I suspect this can be optimized by not running the matching algorithm from the start every time you add an edge but rather keeping the maximum matching and checking if it can be augmented with the newly added edge.