The stable admissions polytope

被引：35

作者：

Baïou, M ^{[1
]}

Balinski, M

机构：

[1] Ecole Polytech, Lab Economet, F-75230 Paris, France

[2] Univ Chile, Dept Ingn Mat, Santiago, Chile

[3] CNRS, Paris, France

来源：

MATHEMATICAL PROGRAMMING | 2000年 / 87卷 / 03期

关键词：

stable assignment; stable marriage; two-sided market; polytopes; graphs; many-to-one matching;

D O I：

10.1007/s101070050004

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The stable admissions polytope - the convex hull of the stable assignments of the university admissions problem - is described by a set of linear inequalities. It depends on a new characterization of stability and arguments that exploit and extend a graphical approach that has been fruitful in the analysis of the stable marriage problem.

引用

页码：427 / 439

页数：13

共 10 条

[1] BAIOU M, 2000, IN PRESS DISCRETE AP
[2] BAIOU M, 1998, ADMISSIONS VIA GRAPH
[3] Graphs and marriages
Balinski, M
Ratier, G
[J]. AMERICAN MATHEMATICAL MONTHLY, 1998, 105 (05) : 430 - 445
[4] BALINSKI M, 1997, SIAM REV, V39, P574
[5] COLLEGE ADMISSIONS AND STABILITY OF MARRIAGE
GALE, D
SHAPLEY, LS
[J]. AMERICAN MATHEMATICAL MONTHLY, 1962, 69 (01) : 9 - &
[6] GROTSCHEL M, 1981, COMBINATORICA, V1, P70
[7] On the stable marriage polytope
Ratier, G
[J]. DISCRETE MATHEMATICS, 1996, 148 (1-3) : 141 - 159
[8] STABLE MATCHINGS, OPTIMAL ASSIGNMENTS, AND LINEAR-PROGRAMMING
ROTH, AE
ROTHBLUM, UG
VANDEVATE, JH
[J]. MATHEMATICS OF OPERATIONS RESEARCH, 1993, 18 (04) : 803 - 828
[9] CHARACTERIZATION OF STABLE MATCHINGS AS EXTREME-POINTS OF A POLYTOPE
ROTHBLUM, UG
[J]. MATHEMATICAL PROGRAMMING, 1992, 54 (01) : 57 - 67
[10] LINEAR-PROGRAMMING BRINGS MARITAL BLISS
VANDEVATE, JH
[J]. OPERATIONS RESEARCH LETTERS, 1989, 8 (03) : 147 - 153

← 1 →