A Note on the Stable Marriage Problem

被引：0

作者：

Zivkovic D. ^{[1
]}

机构：

[1] Faculty of Informatics and Computing, Singidunum University, Belgrade

来源：

SN Computer Science | 2020年 / 1卷 / 2期

关键词：

Combinatorial algorithm; Gale–Shapley algorithm; Matching problem; Stable marriage problem;

D O I：

10.1007/s42979-020-00124-z

中图分类号：

学科分类号：

摘要：

Since the pioneering work of Gale and Shapley, the stable marriage problem has received wide treatment by researchers due to its elegance and applicability. The original problem has been generalized and well studied from different angles, and many algorithms have been proposed for the solution of many variants of the traditional formulation. This short note tries to shed some more light on the original algorithm by providing a more direct proof of its correctness. © 2020, Springer Nature Singapore Pte Ltd.

引用

共 8 条

[1]

Gale D., Shapley L.S., College admissions and the stability of marriage, Am Math Mon, 69, pp. 9-15, (1962)

[2]

Manlove D., Algorithmics of matching under preferences, (2013)

[3]

Knuth D.E., Stable marriage and its relation to other combinatorial problems: an introduction to the mathematical analysis of algorithms, (1997)

[4]

Gusfield D., Three fast algorithms for four problems in stable marriage, SIAM J Comput, 18, pp. 111-128, (1987)

[5]

Gelain M., Pini M.S., Rossi F., Venable K.B., Walsh T., Local search approaches in stable matching problems, Algorithms, 6, pp. 591-617, (2013)

[6]

Manne F., Naim M., Lerring H., Halappanavar M., On stable marriages and greedy matchings, Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing, pp. 92-101, (2016)

[7]

McVitie D.G., Wilson L.B., The stable marriage problem, Commun ACM, 14, 7, pp. 486-490, (1971)

[8]

Tseng S.S., Lee R.C.T., A parallel algorithm to solve the stable marriage problem, BIT, 24, pp. 308-316, (1984)

← 1 →