Given a set of jobs $J$ and a set of machines $M$, where the link between machine $i\in M$ and job $j\in J$ has a positive weight $w_{ij}$. The problem is to select a perfect matching between the jobs and the machines such that the weights of the matching are as close as possible to each other, i.e., the best solution is where all the weights of the matching are equal.

Can we solve this problem in polynomial-time?

  • $\begingroup$ How do you quantify "as close as possible to each other"? $\endgroup$ Apr 14, 2022 at 14:58
  • $\begingroup$ Two selected weights are close to each other when their absolute difference is close to zero. I did not know how to write this mathematically, but I think your assumption is good. $\endgroup$
    – zdm
    Apr 16, 2022 at 1:24

1 Answer 1


You haven't specified what you mean by "as close as possible to each other", so let me assume that you want to minimize the difference between the minimal weight and the maximal weight.

Denote by $m$ the number of edges. Thus, the graph contains at most $m$ different weights. For each pair of weights $a < b$, you can use a perfect matching algorithm to determine whether there is a perfect matching involving only the edges whose weights are in the interval $[a,b]$. After solving $O(m^2)$ many instances of perfect matching, you can find an interval $[a,b]$ supporting a perfect matching and having minimal $b - a$.

There might be smarter algorithms, but this already shows that the problem is solvable in polynomial time.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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