-3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ @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)$. $\endgroup$ – Kaveh Aug 21 '15 at 3:07
3
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ – David Eppstein Aug 21 '15 at 20:09
  • $\begingroup$ Thank you, @DavidEppstein! I've updated the answer accordingly. $\endgroup$ – D.W. Aug 21 '15 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.