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.