7
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ (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. $\endgroup$ – Tsuyoshi Ito Feb 21 '12 at 3:25
10
$\begingroup$

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).

Improve this answer
$\endgroup$
1
  • 7
    $\begingroup$ It's also called the bottleneck assignment problem $\endgroup$ – Ryan Williams Feb 21 '12 at 4:37

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.