1

I have two questions about stable marriage problem.

Given n men and n women, where each person has ranked all members of the opposite sex with an unique number between 1 and n in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are "stable".

I know the solution from http://en.wikipedia.org/wiki/Stable_marriage_problem. The wiki page explains the solution, but it doesn't explain how this solution was inducted.

Q1: Can anyone explain to me how to think of this kind of paring problem? So for similar problems I can have a way of thinking.

Q2: What if we want all possible stable marriage combinations?

Jackson Tale
  • 25,428
  • 34
  • 149
  • 271
  • (1) Experience, creativity and hard work (2) Smells exponential to me – amit Apr 07 '14 at 15:17
  • Often pairing problems are based on some kind of maximum/minimum weight matching, which is totally different from stable marriage. So without knowing what *exactly* you are interested in, we can't tell you. As for Q2, I agree with amit. If you have exponentially many solutions, you don't really need a polynomial-time algorithm. You can just use backtracking with some pruning – Niklas B. Apr 07 '14 at 15:19
  • @G.Bach The weights can't be all equal though. I still think it's exponential – Niklas B. Apr 07 '14 at 15:20
  • I think (2) is a valid question if we talk about output-sensitive polynomial time algorithms. The set of stable marriages may be much smaller than the set of all marriages in some cases even if the stable marriages are exponential. – user2566092 Apr 07 '14 at 15:23

1 Answers1

2

Here is a paper that claims to give an algorithm to enumerate all stable marriages in optimal time and space. The author Dan Gusield is a very reputable computer scientist so it's almost certainly correct.

G. Bach
  • 3,869
  • 2
  • 25
  • 46
user2566092
  • 4,631
  • 15
  • 20
  • Section 2 of that paper also says that there can be exponentially many stable marriages and gives references for it. – G. Bach Apr 07 '14 at 15:47