A straightforward way is for each pair of edge weights $w\leq t$ present in the given graph, try to find a perfect matching in the graph restricted to the edges with weights in the interval $[w,t]$. Among those with a perfect matching, pick one with the smallest value $t-w$ (giving the smallest variance). To speed the things up one can do a kind of binary search over the values $t-w$.
Max Alekseyev
- 34.3k
- 5
- 74
- 152