7
votes
Accepted
Is the bitonic sort algorithm stable?
No, bitonic sort is not stable.
For this post I will denote numbers as 2;0 where only the part before the ; is used for comparison and the part behind ...
7
votes
Another algorithm for stable matching?
There is a totally different algorithm due to Subramanian which uses a fixed point approach. The first idea is to represent the knowledge that we have at any given point in time using intervals, which ...
- 14.1k
6
votes
Another algorithm for stable matching?
Yes, there is a polynomial-time algorithm to find any stable matching.
Understanding the algorithm requires you to study a rotation poset. One of the good materials to learn the rotation poset is ...
4
votes
Another algorithm for stable matching?
There is also a small set of linear constraints that form a polytope whose extreme points are the stable matchings. This allows you to find a stable matching optimizing any linear objective using ...
- 9,800
2
votes
Accepted
Maximum stable matching/allocation
Your problem is equivalent to MAX SMTI (Stable Marriage with Ties and Incomplete lists). You can find the current best approximation algorithm for MAX SMTI in the following paper:
Z. Kiraly, Linear ...
1
vote
Hospital Resident Matching Algorithm with Incomplete Preferences
It's worth noting that some of the great properties that the stable marriage problem has fail in the hospitals and resident model (many-to-one matching). For example, hospital-proposing differed ...
- 163
1
vote
Accepted
Hospital Resident Matching Algorithm with Incomplete Preferences
Yes, in straightforward ways. To accommodate partial lists, the doctors stop proposing after they've been rejected from every hospital in their order, and remain unmatched. The hospitals automatically ...
- 7,022
Only top scored, non community-wiki answers of a minimum length are eligible