0
$\begingroup$

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?

$\endgroup$
3
  • 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$ Jun 4, 2017 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, 2017 at 10:50
  • $\begingroup$ Are you looking for other algorithms solving the stable matching problem? For what reason? $\endgroup$ Jun 5, 2017 at 8:28

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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