Bridging the Gap Between Stable Marriage and Stable Roommates: A Parameterized Algorithm for Optimal Stable Matchings
In the Stable Roommates Problem (SR), a set of $2n$ agents rank one another in a linear order. The goal is to find a matching that is stable: one that has no pair of agents who mutually prefer each other over their assigned partners. We consider the problem of finding an optimal stable matching. Agents associate weights with each of their potential partners, and the goal is to find a stable matching that minimizes the sum of the associated weights. Efficient algorithms exist for finding an optimal stable matching in the Stable Marriage Problem (SM), but the problem is NP-hard for general SR…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.26943
curl -X POST /api/v1/records/arxiv/2603.26943/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.26943/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'