<p>Both problems are easy to solve using standard methods.</p>

<p>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 <span class="math-container">$t$</span> such that a perfect matching exists when you keep only the edges whose weight is <span class="math-container">$\le t$</span>; the running time is <span class="math-container">$O(\lg |V|)$</span> times <a href="https://en.wikipedia.org/wiki/Matching_%28graph_theory%29#Maximum-cardinality_matching" rel="nofollow noreferrer">the running time for unweighted bipartite matching</a>, and there are multiple algorithms for that.  </p>

<p>To solve the second (minimize the total weight of the edges in the matching): This is known as <a href="https://en.wikipedia.org/wiki/Assignment_problem" rel="nofollow noreferrer">the assignment problem</a>; just negate all the edge weights first, then maximize the total weight of the edges in the matching.  There are <a href="https://en.wikipedia.org/wiki/Matching_%28graph_theory%29#In_weighted_bipartite_graphs" rel="nofollow noreferrer">standard algorithms</a> for the assignment problem.</p>

CC BY-SA 3.0
2015-08-21T20:09:14.627Z
For the first part, I would add that this problem is known as bottleneck matching and you can find plenty of literature on it by searching for that phrase.
David Eppstein
CC BY-SA 3.0
2015-08-21T21:08:51.027Z
Thank you, @DavidEppstein!  I've updated the answer accordingly.
D.W.
CC BY-SA 4.0
2015-08-21T15:31:48.453Z
2020-03-31T20:30:11.810Z
2020-03-31T20:30:11.810Z
D.W.
<p>Consider the following matching problem:</p>

<p><strong>Input</strong>: 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]$.</p>

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

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

<p>Note that $[n] = \{1, 2, /\ldots, n\}$.<br>
Originally <a href="https://math.stackexchange.com/q/1396061/">posted</a> on MSE.</p>

CC BY-SA 3.0
2015-08-21T03:07:48.967Z
@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)$.
Kaveh
<ds.algorithms><graph-algorithms><matching>
Weighted matching algorithm for minimizing max weight
user259631
# Weighted matching algorithm for minimizing max weight

(Asked by: username_0 on 2015-08-19)

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](https://math.stackexchange.com/q/1396061/) on MSE.

**Tags:** ds.algorithms, graph-algorithms, matching

> **Comments:**
> **username_1**: @username_2, 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)$.  

---

## 1 answers

### Answer by username_2 on 2015-08-21. Score: 3

Both problems are easy to solve using standard methods.

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 username_3 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](https://en.wikipedia.org/wiki/Matching_%28graph_theory%29#Maximum-cardinality_matching), and there are multiple algorithms for that.

To solve the second (minimize the total weight of the edges in the matching): This is known as [the assignment problem](https://en.wikipedia.org/wiki/Assignment_problem); just negate all the edge weights first, then maximize the total weight of the edges in the matching. There are [standard algorithms](https://en.wikipedia.org/wiki/Matching_%28graph_theory%29#In_weighted_bipartite_graphs) for the assignment problem.

> **Comments:**
> **username_3**: For the first part, I would add that this problem is known as bottleneck matching and you can find plenty of literature on it by searching for that phrase.  
> **username_2**: Thank you, @DavidEppstein!  I've updated the answer accordingly.  

---

