3
$\begingroup$

Given an undirected graph $G = (V,E)$, edge weight $w_e \ \forall e \in E$, I'm interested in the following problem.

Find a perfect matching $M \subseteq E$ that minimizes $(\max_{e \in M} w_e - \min_{e \in M} w_e)$.

Does this problem generalize/reduce to an existing problem? I can find max weight perfect matching, but not exactly a "balanced weight perfect matching". Any thoughts would be helpful.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.