<p>Your problem is called maximum weighted simple b-matching, and it's solvable in strongly polynomial time. See <a href="http://web.archive.org/web/20150920041722/http://web.eecs.umich.edu/~pettie/matching/Muller-Hannemann-Schwartz-b-matching.pdf" rel="nofollow">this paper</a> for instance.</p>

CC BY-SA 3.0
2015-09-24T17:06:54.217Z
Thank you!  Even better, there are simple, fast, good approximation algorithms: http://web.eecs.umich.edu/~pettie/matching/Hougardy-linear-time-approx-DCS.pdf
Doctor J
CC BY-SA 3.0
2015-09-23T07:31:21.497Z
2015-09-23T07:31:21.497Z
didest
<p>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.</p>

<p>I believe this can be seen as an instance of the <a href="http://www.sciencedirect.com/science/article/pii/S0166218X07001552" rel="nofollow">Stable Fixtures Problem</a> (itself a generalization of the <a href="https://en.wikipedia.org/wiki/Stable_roommates_problem" rel="nofollow">Stable Roommates Problem</a>), 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.</p>

<p>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.</p>

<ds.algorithms><co.combinatorics><approximation-algorithms><matching><heuristics>
Approximations for the Stable Fixtures Problem
Doctor J
# Approximations for the Stable Fixtures Problem

(Asked by: username_0 on 2015-09-22)

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](http://www.sciencedirect.com/science/article/pii/S0166218X07001552) (itself a generalization of the [Stable Roommates Problem](https://en.wikipedia.org/wiki/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.

**Tags:** ds.algorithms, co.combinatorics, approximation-algorithms, matching, heuristics


---

## 1 answers

### Answer by username_1 on 2015-09-23. Score: 1 | Accepted answer

Your problem is called maximum weighted simple b-matching, and it's solvable in strongly polynomial time. See [this paper](http://web.archive.org/web/20150920041722/http://web.eecs.umich.edu/~pettie/matching/Muller-Hannemann-Schwartz-b-matching.pdf) for instance.

> **Comments:**
> **username_0**: Thank you!  Even better, there are simple, fast, good approximation algorithms: http://web.eecs.umich.edu/~pettie/matching/Hougardy-linear-time-approx-DCS.pdf  

---

