Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

Hot answers tagged

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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 7,022

Only top scored, non community-wiki answers of a minimum length are eligible