| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 1718.1 | Reason for posting | TLE::REINIG | This too shall change | Thu Feb 18 1993 11:31 | 6 |
| It's a homework assignment I haven't been able to solve. I'm looking
for hints on how to procede. Since the assignment is due 2/19/93,
if you have qualms about providing such hints, you need only wait until
the 20 to post.
August G. Reinig
|
| 1718.2 | | STOHUB::SLBLUZ::BROCKUS | I'm the NRA. | Thu Feb 18 1993 16:49 | 9 |
| >> A Marriage is a perfect matching between the boys and the
>> girls.
Could you further describe what the above means? I can see 2 different
interpretations of it.
Thanks.
JPB
|
| 1718.3 | My interpretation | TLE::REINIG | This too shall change | Thu Feb 18 1993 18:29 | 5 |
| My understanding is that you pair each boy with one girl and vice
versa, so that you have n pairs. Can you do so in such a way that each
pair is stable?
August
|
| 1718.4 | | CSC32::D_DERAMO | Dan D'Eramo, Customer Support Center | Fri Feb 19 1993 16:43 | 9 |
| A plausible approach is to come up with an algorithm which
given an assignment with at least one unstable pair, will
always munge it into an assignment with at least one fewer
unstable pair.
If you can do that, then the smallest k such that there is an
assignment with exactly k unstable pairs, has to be k=0.
Dan
|
| 1718.5 | Solution | TLE::REINIG | This too shall change | Fri Feb 19 1993 18:21 | 29 |
| 1718.6 | poor D! | HERON::BUCHANAN | The was not found. | Mon Feb 22 1993 14:31 | 27 |
| > In a group of n boys and n girls, each girl ranks the n boys according
> to her preference and each boy ranks the n girls according to his
> preference. A Marriage is a perfect matching between the boys and the
> girls. A marriage is unstable if there is a pair who are not married
> to each other but like each other more than they like their respective
> spouses; otherwise, it is stable. Prove that a stable marriage always
> exists.
Generalize the problem: consider 2*n monogamous bisexuals. Each
individual ranks all the 2*n-1 others. Retain exactly the same definition of
stability as worded above. Does a stable Marriage still exist?
Not necessarily.
Suppose that there are 4 individuals: labeled imaginatively A,B,C & D.
Let the preferences be as follows:
A: prefers B over C over D
B: prefers C over A over D
C: prefers A over B over D
D: irrelevant
Suppose that a Marriage exists. By symmetry we may suppose that it's
A+B & C+D. But B & C are yearningly attracted to one another more than they
are to their respective spouses.
Andrew.
|
| 1718.7 | linear assignment | NOVA::FINNERTY | Sell high, buy low | Tue Mar 08 1994 19:54 | 9 |
|
The algorithm for bipartite matching is usually called 'linear
assignment'. If the boys rank each girl in order of preference, the
solution to the linear assignment problem is a 'stable marriage'.
regret to say that this is only boy-optimal, though.
;)
|