I have been searching for matching algorithms similar to the Gale Shapley, or stable marriage algorithm, but with no luck. The question is if there are other algorithms that are similar to the GS and used for the assignation of persons or items based on preferences?

  • 3
    $\begingroup$ What do you mean by "similar"? Gale-Shapley solves a specific problem (the stable marriage problem). Are you looking for other algorithms for the same problem? Other problems that are somehow similar to that problem? Or something else? And suppose somebody does give you a list of "similar" algorithms or problems -- what actual use is that list to you? I find your question and its motivation rather unclear. $\endgroup$ – David Richerby Jun 4 '17 at 9:17
  • $\begingroup$ @DavidRicherby, I am looking for other algorithms that could solve that problem. The thing is that I was no able to find that $\endgroup$ – Layla Jun 4 '17 at 10:50
  • $\begingroup$ Are you looking for other algorithms solving the stable matching problem? For what reason? $\endgroup$ – Yuval Filmus Jun 5 '17 at 8:28

A very similar well studied problem is the assignment problem. In essence, it seeks to find a matching in a weighted bipartite graph that has maximum weight. Such matching is not necessarily stable, but maximum weighted matching might be preferable than a stable one, depending on the application.

On the plus side, the well known Hungarian algorithm solves the assignment problem in an optimal manner. There are also other methods to solve it such as the Auction algorithms. As I said, the field includes well established methods.

Maybe you can think about representing your problem as an assignment one rather than stable marriage.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.