Stable matchings and linear programming

被引：10

作者：

Abeledo, H ^{[1
]}

Blum, Y ^{[1
]}

机构：

[1] TECHNION ISRAEL INST TECHNOL,FAC IND ENGN & MANAGEMENT,IL-23000 HAIFA,ISRAEL

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 1996年 / 245卷 / 245期

关键词：

D O I：

10.1016/0024-3795(95)00052-6

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

This paper continues the work of Abeledo and Rothblum, who study nonbipartite stable matching problems from a polyhedral perspective. We establish here additional properties of fractional stable matchings and use linear programming to obtain an alternative polynomial algorithm for solving stable matching problems.

引用

页码：321 / 333

页数：13

共 15 条

[1] A CHARACTERIZATION OF GRAPHS THAT ENSURE THE EXISTENCE OF STABLE MATCHINGS [J].

ABELEDO, H ;

ISAAK, G .

MATHEMATICAL SOCIAL SCIENCES, 1991, 22 (01) :93-96

[2] STABLE MATCHINGS AND LINEAR INEQUALITIES [J].

ABELEDO, HG ;

ROTHBLUM, UG .

DISCRETE APPLIED MATHEMATICS, 1994, 54 (01) :1-27

[3]

[Anonymous], 1979, Graph Theory: An Introductory Course

[4]

FEDER R, 1989, 21 ANN S THEOR COMP

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

GALE, D ;

SHAPLEY, LS .

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

[6]

Gusfield D., 1989, STABLE MARRIAGE PROB

[7] AN EFFICIENT ALGORITHM FOR THE STABLE ROOMMATES PROBLEM [J].

IRVING, RW .

JOURNAL OF ALGORITHMS, 1985, 6 (04) :577-595

[8]

KARP R, 1980, P 21 ANN S FDN COMP, P1

[9]

Knuth D, 1976, Mariages stables

[10]

PULLEYBLANK WR, 1983, MATH PROGRAMMING STA, P312

← 1 2 →