Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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 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.
To solve the second (minimize the total weight of the edges in the matching): This is known as the assignment problem; just negate all the edge weights first, then maximize the total weight of the edges in the matching. There are standard algorithms for the assignment problem.
