# Assignment problem with sum replaced by max

In the assignment problem, one tries to find $f$ such that the cost function $$\sum_{a\in A} C(a,f(a))$$ is minimized. Here $f$ is a bijection between sets $A$ and $B$ of equal finite cardinality, and $C$ is a cost function $A\times B \to \mathbb R$.

My question: is there a name for the problem to minimize $$\max_{a\in A} \, C(a,f(a))$$ over bijections $f$ as above?

Thanks in advance for any replies or references.

• (1) I think that I have seen this variant on this website, but I cannot locate it. (2) Because the answer is one of the values of C, you can use binary search. But maybe there is a faster algorithm. – Tsuyoshi Ito Feb 21 '12 at 3:25

## 1 Answer

In the geometric setting, where $C(x,y) = \|x - y \|$, this formulation is called the bottleneck matching problem. It's possible that this is the generic term for it (I've seen this formulation used in the Kleinberg-Tardos algorithms book for MSTs).

• It's also called the bottleneck assignment problem – Ryan Williams Feb 21 '12 at 4:37