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.


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.