Faster and Simpler Approximation of Stable Matchings

Algorithms

关键词: stable matching;    stable marriage;    approximation algorithm;   

DOI  :  10.3390/a7020189

来源: mdpi

【 摘 要 】

We give atime, where n denotes the number of people and m is the total length of the preference lists in a given instance. In addition, the algorithm and the analysis are much simpler. We also give the extension of the algorithm for computing stablemany-to-many matchings.

【 授权许可】

CC BY   
© 2014 by the author; licensee MDPI, Basel, Switzerland.