1
$\begingroup$

I have a set of N items, each with a subset of those items they can be paired with; each pair has a weight. I'd like to choose pairs to maximize the total weight, subject to each item being in at most M pairs.

I believe this can be seen as an instance of the Stable Fixtures Problem (itself a generalization of the Stable Roommates Problem), which seeks to find a stable matching if one exists. However, I don't really care if the matching is stable, and I want to find a high-weight matching in every case. It doesn't need to be optimal, approximate is fine.

Are there any approximate solutions for this problem, or does this problem go by another name in another field? Approaches I can think of would be to randomly perturb the ranks (weights) until a stable matching is found, or perhaps treat it as a linear programming problem.

$\endgroup$
1
$\begingroup$

Your problem is called maximum weighted simple b-matching, and it's solvable in strongly polynomial time. See this paper for instance.

$\endgroup$

Your Answer

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

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