|Table of Contents|

The Extensions on Gale Shapley Matching(PDF)

《南京理工大学学报》(自然科学版)[ISSN:1005-9830/CN:32-1397/N]

Issue:
1997年06期
Page:
93-97
Research Field:
Publishing date:

Info

Title:
The Extensions on Gale Shapley Matching
Author(s):
LianGuangchang ZhuShunrong ①
Nanjing Polyt echnic College,Nanjing 210008
① School of Sciences,NUST,Nanjing 210094
Keywords:
Gale-Shapley mat ching man-opt imal matching woman-opt imal matching complet e bipart it e graph.
PACS:
O241
DOI:
-
Abstract:
 T he man-optimal algorithm in the Gale-Shapley mat ching is ex tended in this paper. T he most st ages for the G-S matching is n 2 - n+ 1 when we admit some boys may not select at each st age. It is generalized t o general cases: when there arem boys and n girles ( m ≠n ) , the most st ages f or the man-opt imal algorithm in the G-S matching is m(m - 1) + 1 ( when m ≤ n) or n( m - 1) + 1 (w hen m > n) , and the most st ages f or the women-opt imal algorithm is n( n - 1) + 1 ( when n ≤ m) or m(n - 1) + 1 ( w hen n > m) .

References:

1 Gale D, Shapley L S. Colley e admissions a nd the st ability o f ma rr iag e. Amer M ath Monthly,1962, 69: 9~14
2 Eug ene L, Low ler . Combinato rial optimiza tio n. Netw or ks and Mat ro ids, Ho lt , Rinehart and Winston, San Fr ancisco , 1976 211~213

Memo

Memo:
-
Last Update: 2013-03-29