Popular matchings

被引：103

作者：

Abraham, David J. ^{[1
]}

Irving, Robert W. ^{[2
]}

Kavitha, Telikepalli ^{[3
]}

Mehlhorn, Kurt ^{[4
]}

机构：

[1] Carnegie Mellon Univ, Dept Comp Sci, Pittsburgh, PA 15213 USA

[2] Univ Glasgow, Dept Comp Sci, Glasgow G12 8RZ, Lanark, Scotland

[3] Indian Inst Sci, Comp Sci & Automat, Bangalore 560012, Karnataka, India

[4] Max Planck Inst Informat, Dept Algorithms & Complex, D-66123 Saarbrucken, Germany

来源：

SIAM JOURNAL ON COMPUTING | 2007年 / 37卷 / 04期

关键词：

matchings; bipartite graphs; one-sided preference lists;

D O I：

10.1137/06067328X

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider the problem of matching a set of applicants to a set of posts, where each applicant has a preference list, ranking a nonempty subset of posts in order of preference, possibly involving ties. We say that a matching M is popular if there is no matching M' such that the number of applicants preferring M' to M exceeds the number of applicants preferring M to M'. In this paper, we give the first polynomial-time algorithms to determine if an instance admits a popular matching and to find a largest such matching, if one exists. For the special case in which every preference list is strictly ordered (i. e., contains no ties), we give an O(n + m) time algorithm, where n is the total number of applicants and posts and m is the total length of all of the preference lists. For the general case in which preference lists may contain ties, we give an O(root nm) time algorithm.

引用

页码：1030 / 1045

页数：16

共 20 条

[1] Random serial dictatorship and the core from random endowments in house allocation problems [J].

Abdulkadiroglu, A ;

Sonmez, T .

ECONOMETRICA, 1998, 66 (03) :689-701

[2]

Abraham DJ, 2006, LECT NOTES COMPUT SC, V4059, P65

[3]

Abraham DJ, 2005, PROCEEDINGS OF THE SIXTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P424

[4]

Abraham DJ, 2004, LECT NOTES COMPUT SC, V3341, P3

[5] COLLEGE ADMISSIONS AND STABILITY OF MARRIAGE [J].

GALE, D ;

SHAPLEY, LS .

AMERICAN MATHEMATICAL MONTHLY, 1962, 69 (01) :9-&

[6] MATCH MAKING - ASSIGNMENTS BASED ON BILATERAL PREFERENCES [J].

GARDENFORS, P .

BEHAVIORAL SCIENCE, 1975, 20 (03) :166-173

[7]

GUSFIELD D, 1989, STABEL MARRIAGE PROB

[8]

Hall P, 1935, J. Lond. Math. Soc., Vs1-10, P26, DOI DOI 10.1112/JLMS/S1-10.37.26

[9]

Hopcroft J. E., 1973, SIAM Journal on Computing, V2, P225, DOI 10.1137/0202019

[10] EFFICIENT ALLOCATION OF INDIVIDUALS TO POSITIONS [J].

HYLLAND, A ;

ZECKHAUSER, R .

JOURNAL OF POLITICAL ECONOMY, 1979, 87 (02) :293-314

← 1 2 →