Maximum Locally Stable Matchings

Algorithms

Christine T. Cheng¹ 

[1] Department of Computer Science, University of Wisconsin-Milwaukee, 3200 N. Cramer Street, Milwaukee, WI 53211, USA

关键词: stable matchings;    hospital/residents problem;    social networks;   

DOI  :  10.3390/a6030383

来源: mdpi

【 摘 要 】

Motivated by the observation that most companies are more likely to consider job applicants referred by their employees than those who applied on their own, Arcaute and Vassilvitskii modeled a job market that integrates social networks into stable matchings in an interesting way. We call their model HR+SN because an instance of their model is an ordered pairwho can then forward it to h. A locally stable matching is a matching with no local blocking pairs. The cardinality of the locally stable matchings of I can vary. This paper presents a variety of results on computing a locally stable matching with maximum cardinality.

【 授权许可】

CC BY   
© 2013 by the authors; licensee MDPI, Basel, Switzerland.