# Weighted matching algorithm for minimizing max weight

Consider the following matching problem:

Input: a complete weighted bipartite graph with $n+m$ vertices, given by $n$, $m$, and $w_{i}$ a permutation of $[m]$ for each $i \in [n]$.

Output: a matching $M: [n] \rightarrowtail [m]$ which minimized the following function: $$cost(M) = \max_{i\in[n]} w_{i,M(i)}$$

What is the fastest known algorithm for this problem?
What if I want to minimize $\sum_{i\in[n]} w_{i, M(i)}$?

Note that $[n] = \{1, 2, /\ldots, n\}$.
Originally posted on MSE.

• @D.W., I think the question is quite simple: you want a matching from [n] to [m] ($w$ is the weights of edges) and you want to minimize max weight in the matching. $w_{M(i)}$ is the weight of the edge from $i$ to $M(i)$. Aug 21, 2015 at 3:07

To solve the first (minimize the maximum weight of the edges in the matching): This problem is known as bottleneck matching, and you can find plenty of literature on it by searching for that phrase (thanks to David Eppstein for pointing this out). One simple approach is to sort the edge weights, then use binary search to find the smallest threshold $$t$$ such that a perfect matching exists when you keep only the edges whose weight is $$\le t$$; the running time is $$O(\lg |V|)$$ times the running time for unweighted bipartite matching, and there are multiple algorithms for that.