STABLE MATCHINGS AND LINEAR INEQUALITIES

被引：23

作者：

ABELEDO, HG

ROTHBLUM, UG

机构：

[1] RUTGERS STATE UNIV,RUTGERS CTR OPERAT RES,NEW BRUNSWICK,NJ 08903

[2] TECHNION ISRAEL INST TECHNOL,FAC IND ENGN & MANAGEMENT,IL-32000 HAIFA,ISRAEL

来源：

DISCRETE APPLIED MATHEMATICS | 1994年 / 54卷 / 01期

关键词：

D O I：

10.1016/0166-218X(94)90130-9

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The theory of linear inequalities and linear programming was recently applied to study the stable marriage problem which until then has been studied by mostly combinatorial methods. Here we extend the approach to the general stable matching problem in which the structure of matchable pairs need not be bipartite. New issues arise in the analysis and we combine linear algebra and graph theory to explore them.

引用

页码：1 / 27

页数：27

共 20 条

[1]

ABELEDO H, 1991, MATH SOCIAL SCI, V22

[2]

ABELEDO H, 1993, THESIS

[3]

[Anonymous], 1989, STABLE MARRIAGE PROB

[4] INTEGER PROGRAMMING - METHODS, USES, COMPUTATION [J].

BALINSKI, ML .

MANAGEMENT SCIENCE, 1965, 12 (03) :253-313

[5]

Birkoff G, 1946, U NAC TUCUMAN REV SE, V5, P147

[6] MAXIMUM MATCHING AND A POLYHEDRON WITH O'1-VERTICES [J].

EDMONDS, J .

JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICS AND MATHEMATICAL, 1965, B 69 (1-2) :125-+

[7]

FEDER T, 1989, P ANN S THEOREM COMP

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

GALE, D ;

SHAPLEY, LS .

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

[9]

HARTMANN M, 1990, UNCORTR9018 U N CAR

[10] AN EFFICIENT ALGORITHM FOR THE OPTIMAL STABLE MARRIAGE [J].

IRVING, RW ;

LEATHER, P ;

GUSFIELD, D .

JOURNAL OF THE ACM, 1987, 34 (03) :532-543

← 1 2 →