-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.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ 1. The problem is not well defined. It's not clear what it means to "minimize $l$ overall $k$". That's not a single objective function, so it's not clear what solution you want. 2. Was there something wrong with the answer Chester gave you over on Math.SE? We expect you to mention in the question all approaches you've considered and rejected, and tell us why. If you want to minimize the sum of unhappiness, this is exactly the assignment problem, and this is not a research-level question, so it's off-topic here. $\endgroup$ – D.W. Aug 19 '15 at 16:05
  • $\begingroup$ I appreciate the edit but now I think there's something not quite right yet about the problem formulation. I'm not sure what the $w_i$ but apparently they are never used, which looks like something has gone wrong. In any case, it doesn't look like a research-level question: minimizing the maximum unhappiness can be done by a straightforward algorithm (sort the edge weights...); and I already described how to minimize the total unhappiness. $\endgroup$ – D.W. Aug 20 '15 at 22:07
  • $\begingroup$ Thanks, @Kaveh. Another confusion: Apparently $w_i$ is a permutation. So what does it mean to take a max over multiple permutations? Or a sum? Perhaps $w_{M(i)}$ should be $w_{M(i)}(i)$ or something like that? That said, further edits to polish the presentation are probably pointless, as this does not seem to be research-level. $\endgroup$ – D.W. Aug 21 '15 at 2:33
  • $\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
2
$\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.

|cite|improve this answer
$\endgroup$
  • 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.