Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(7)
Medical Students
Polynomial Time
Polynomial Time Algorithm
Solution Concept
Stable Marriage Problem
Stable Matching
Stable Marriage
Subscribe
Academic
Publications
Stable marriage with ties and bounded length preference lists
Stable marriage with ties and bounded length preference lists,10.1016/j.jda.2008.09.003,Journal of Discrete Algorithms,Robert W. Irving,David F. Manlo
Edit
Stable marriage with ties and bounded length preference lists
(
Citations: 4
)
BibTex

RIS

RefWorks
Download
Robert W. Irving
,
David F. Manlove
,
Gregg O'malley
We consider variants of the classical
stable marriage problem
in which preference lists may contain ties, and may be of bounded length. Such restrictions arise naturally in practical applications, such as centralised matching schemes that assign graduating
medical students
to their first hospital posts. In such a setting, weak stability is the most common solution concept, and it is known that weakly stable matchings can have different sizes. This motivates the problem of finding a maximum cardinality weakly stable matching, which is known to be NPhard in general. We show that this problem is solvable in
polynomial time
if each man's list is of length at most 2 (even for women's lists that are of unbounded length). However if each man's list is of length at most 3, we show that the problem becomes NPhard (even if each women's list is of length at most 3) and not approximable within some δ>1 (even if each woman's list is of length at most 4).
Journal:
Journal of Discrete Algorithms  JDA
, vol. 7, no. 2, pp. 213219, 2009
DOI:
10.1016/j.jda.2008.09.003
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.sciencedirect.com
)
(
dx.doi.org
)
(
www.informatik.unitrier.de
)
(
linkinghub.elsevier.com
)
More »
Citation Context
(2)
...If the length of each man’s list is bounded by 2, it is solvable in polynomial time even if women’s lists are of arbitrary length, while it is NPhard even if the length of each preference list is bounded by 3 [
8
]...
Kazuo Iwama
,
et al.
A 25/17Approximation Algorithm for the Stable Marriage Problem with On...
...problem of nding a stable matching of maximum cardinality (henceforth a maximum stable matching) for an instance of HRT { problem MAXHRT { is NPhard [20,
15
], even under severe restrictions...
...Also, MAXHRT is NPhard even if each hospital has capacity 1, each preference list is of length at most 3, and each resident’s list is strictly ordered [
15
]...
Robert W. Irving
,
et al.
Finding large stable matchings
References
(11)
Faster Scaling Algorithms for Network Problems
(
Citations: 200
)
Harold N. Gabow
,
Robert Endre Tarjan
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 18, no. 5, pp. 10131036, 1989
College admissions and the stability of marriage
(
Citations: 1234
)
D. Gale
,
L. S. Shapley
Published in 1962.
Some remarks on the stable matching problem
(
Citations: 120
)
David Gale
,
Marilda Sotomayor
Journal:
Discrete Applied Mathematics  DAM
, vol. 11, no. 3, pp. 223232, 1985
Some Simplified NPComplete Graph Problems
(
Citations: 734
)
M. R. Garey
,
David S. Johnson
,
Larry J. Stockmeyer
Journal:
Theoretical Computer Science  TCS
, vol. 1, no. 3, pp. 237267, 1976
The Stable marriage problem  structure and algorithms
(
Citations: 311
)
Dan Gusfield
,
Robert W. Irving
Published in 1989.
Sort by:
Citations
(4)
Almost Stable Matchings by Truncating the GaleShapley Algorithm
(
Citations: 5
)
Patrik Floréen
,
Petteri Kaski
,
Valentin Polishchuk
,
Jukka Suomela
Journal:
Algorithmica
, vol. 58, no. 1, pp. 102118, 2010
Keeping partners together: algorithmic results for the hospitals/residents problem with couples
(
Citations: 2
)
Eric J. McDermid
,
David F. Manlove
Journal:
Journal of Combinatorial Optimization  JCO
, vol. 19, no. 3, pp. 279303, 2010
A 25/17Approximation Algorithm for the Stable Marriage Problem with OneSided Ties
Kazuo Iwama
,
Shuichi Miyazaki
,
Hiroki Yanagisawa
Conference:
European Symposium on Algorithms  ESA
, pp. 135146, 2010
Finding large stable matchings
(
Citations: 3
)
Robert W. Irving
,
David F. Manlove
Journal:
ACM Journal of Experimental Algorithms  JEA
, vol. 14, pp. 1.21.30, 2009