<p>In the geometric setting, where $C(x,y) = \|x - y \|$, this formulation is called the <strong><em>bottleneck matching problem</em></strong>. 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). </p>

CC BY-SA 3.0
2012-02-21T04:37:26.273Z
It's also called the bottleneck assignment problem
Ryan Williams
CC BY-SA 3.0
2012-02-21T04:15:30.857Z
2012-02-21T04:15:30.857Z
Suresh Venkat
<p>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$.</p>

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

<p>Thanks in advance for any replies or references.</p>

CC BY-SA 3.0
2012-02-21T03:25:20.620Z
(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
<ds.algorithms><reference-request><optimization><linear-programming>
Assignment problem with sum replaced by max
N20
# Assignment problem with sum replaced by max

(Asked by: username_0 on 2012-02-21)

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.

**Tags:** ds.algorithms, reference-request, optimization, linear-programming

> **Comments:**
> **username_1**: (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.  

---

## 1 answers

### Answer by username_2 on 2012-02-21. Score: 10 | Accepted 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).

> **Comments:**
> **username_3**: It's also called the bottleneck assignment problem  

---

