CHARACTERIZATION OF STABLE MATCHINGS AS EXTREME-POINTS OF A POLYTOPE

被引：80

作者：

ROTHBLUM, UG ^{[1
]}

机构：

[1] RUTGERS STATE UNIV,HILL CTR MATH SCI,RUTGERS CTR OPERAT RES,NEW BRUNSWICK,NJ 08904

来源：

MATHEMATICAL PROGRAMMING | 1992年 / 54卷 / 01期

关键词：

MATCHINGS; STABILITY; EXTREME POINTS; POLYTOPE;

D O I：

10.1007/BF01586041

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The purpose of this paper is to extend a modified version of a recent result of Vande Vate (1989) which characterizes stable matchings as the extreme points of a certain polytope. Our proofs are simpler and more transparent than those of Vande Vate.

引用

页码：57 / 67

页数：11

共 7 条

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

GALE, D ;

SHAPLEY, LS .

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

[2]

Gusfield D., 1989, STABLE MARRIAGE PROB

[3]

Knuth D., 1976, MARIAGES STABLES

[4] THE COLLEGE ADMISSIONS PROBLEM IS NOT EQUIVALENT TO THE MARRIAGE PROBLEM [J].

ROTH, AE .

JOURNAL OF ECONOMIC THEORY, 1985, 36 (02) :277-288

[5] THE EVOLUTION OF THE LABOR-MARKET FOR MEDICAL INTERNS AND RESIDENTS - A CASE-STUDY IN GAME-THEORY [J].

ROTH, AE .

JOURNAL OF POLITICAL ECONOMY, 1984, 92 (06) :991-1016

[6]

ROTH AE, 1991, ECONOMETRIC SOC MONO

[7] LINEAR-PROGRAMMING BRINGS MARITAL BLISS [J].

VANDEVATE, JH .

OPERATIONS RESEARCH LETTERS, 1989, 8 (03) :147-153

← 1 →