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.
