An efficient implementation of the Gale and Shapley "propose-and-reject" algorithm

Electronic Journal of Graph Theory and Applications

卷:8

Evi Papaioannou¹  Christos Kaklamanis¹  Nasia Zacharia² 

[1] University of Patras & CTI "Diophantus";

[2] University of Patras;

关键词: stable matching;    gale and shapley algorithm;    the firms/candidates problem;    efficient implementation;    "propose-and-reject" algorithm;   

DOI  :  10.5614/ejgta.2020.8.1.4

来源: DOAJ

【 摘 要 】

We consider a version of the Hospitals/Residents problem which was first defined in 1962 by Gale and Shapley [9] under the name "College Admissions Problem". In particular, we consider the Firms/Candidates problem, where each Firm wishes to hire at least one Candidate and each Candidate can be finally assigned to a single Firm. We present an efficient implementation of the Gale and Shapley "propose-and-reject" algorithm when applied to the case of the Firms/Candidates problem.

【 授权许可】

Unknown