# Find a perfect matching with weights as close as possible to each other

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?

• How do you quantify "as close as possible to each other"? Apr 14, 2022 at 14:58
• 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.
– zdm
Apr 16, 2022 at 1:24

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