Stable matchings with ties, master preference lists, and matroid constraints

Naoyuki Kamiyama

doi:10.1007/978-3-662-48433-3_1

Stable matchings with ties, master preference lists, and matroid constraints

Naoyuki Kamiyama

Division of Advanced Mathematics Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

8 Citations (Scopus)

Abstract

In this paper, we consider a matroid generalization of the hospitals/residents problem with ties and master lists. In this model, the capacity constraints for hospitals are generalized to matroid constraints. By generalizing the algorithms of O’Malley for the hospitals/residents problem with ties and master lists, we give polynomial-time algorithms for deciding whether there exist a super-stable matching and a strongly stable matching in our model, and finding such matchings if they exist.

Original language	English
Title of host publication	Algorithmic Game Theory - 8th International Symposium, SAGT 2015
Editors	Martin Hoefer, Martin Hoefer
Publisher	Springer Verlag
Pages	3-14
Number of pages	12
ISBN (Print)	9783662484326
DOIs	https://doi.org/10.1007/978-3-662-48433-3_1
Publication status	Published - 2015
Event	8th International Symposium on Algorithmic Game Theory, SAGT 2015 - Saarbrucken, Germany Duration: Sept 28 2015 → Sept 30 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9347
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	8th International Symposium on Algorithmic Game Theory, SAGT 2015
Country/Territory	Germany
City	Saarbrucken
Period	9/28/15 → 9/30/15

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-662-48433-3_1

Cite this

Kamiyama, N. (2015). Stable matchings with ties, master preference lists, and matroid constraints. In M. Hoefer, & M. Hoefer (Eds.), Algorithmic Game Theory - 8th International Symposium, SAGT 2015 (pp. 3-14). Article A1 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9347). Springer Verlag. https://doi.org/10.1007/978-3-662-48433-3_1

Stable matchings with ties, master preference lists, and matroid constraints. / Kamiyama, Naoyuki.
Algorithmic Game Theory - 8th International Symposium, SAGT 2015. ed. / Martin Hoefer; Martin Hoefer. Springer Verlag, 2015. p. 3-14 A1 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9347).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kamiyama, N 2015, Stable matchings with ties, master preference lists, and matroid constraints. in M Hoefer & M Hoefer (eds), Algorithmic Game Theory - 8th International Symposium, SAGT 2015., A1, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9347, Springer Verlag, pp. 3-14, 8th International Symposium on Algorithmic Game Theory, SAGT 2015, Saarbrucken, Germany, 9/28/15. https://doi.org/10.1007/978-3-662-48433-3_1

Kamiyama N. Stable matchings with ties, master preference lists, and matroid constraints. In Hoefer M, Hoefer M, editors, Algorithmic Game Theory - 8th International Symposium, SAGT 2015. Springer Verlag. 2015. p. 3-14. A1. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-48433-3_1

Kamiyama, Naoyuki. / Stable matchings with ties, master preference lists, and matroid constraints. Algorithmic Game Theory - 8th International Symposium, SAGT 2015. editor / Martin Hoefer ; Martin Hoefer. Springer Verlag, 2015. pp. 3-14 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f12fa3522e9a44ad81ab8711c528a9e3,

title = "Stable matchings with ties, master preference lists, and matroid constraints",

abstract = "In this paper, we consider a matroid generalization of the hospitals/residents problem with ties and master lists. In this model, the capacity constraints for hospitals are generalized to matroid constraints. By generalizing the algorithms of O{\textquoteright}Malley for the hospitals/residents problem with ties and master lists, we give polynomial-time algorithms for deciding whether there exist a super-stable matching and a strongly stable matching in our model, and finding such matchings if they exist.",

author = "Naoyuki Kamiyama",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2015.; 8th International Symposium on Algorithmic Game Theory, SAGT 2015 ; Conference date: 28-09-2015 Through 30-09-2015",

year = "2015",

doi = "10.1007/978-3-662-48433-3_1",

language = "English",

isbn = "9783662484326",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "3--14",

editor = "Martin Hoefer and Martin Hoefer",

booktitle = "Algorithmic Game Theory - 8th International Symposium, SAGT 2015",

address = "Germany",

}

TY - GEN

T1 - Stable matchings with ties, master preference lists, and matroid constraints

AU - Kamiyama, Naoyuki

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2015.

PY - 2015

Y1 - 2015

N2 - In this paper, we consider a matroid generalization of the hospitals/residents problem with ties and master lists. In this model, the capacity constraints for hospitals are generalized to matroid constraints. By generalizing the algorithms of O’Malley for the hospitals/residents problem with ties and master lists, we give polynomial-time algorithms for deciding whether there exist a super-stable matching and a strongly stable matching in our model, and finding such matchings if they exist.

AB - In this paper, we consider a matroid generalization of the hospitals/residents problem with ties and master lists. In this model, the capacity constraints for hospitals are generalized to matroid constraints. By generalizing the algorithms of O’Malley for the hospitals/residents problem with ties and master lists, we give polynomial-time algorithms for deciding whether there exist a super-stable matching and a strongly stable matching in our model, and finding such matchings if they exist.

UR - http://www.scopus.com/inward/record.url?scp=84983788976&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84983788976&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-48433-3_1

DO - 10.1007/978-3-662-48433-3_1

M3 - Conference contribution

AN - SCOPUS:84983788976

SN - 9783662484326

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 3

EP - 14

BT - Algorithmic Game Theory - 8th International Symposium, SAGT 2015

A2 - Hoefer, Martin

PB - Springer Verlag

T2 - 8th International Symposium on Algorithmic Game Theory, SAGT 2015

Y2 - 28 September 2015 through 30 September 2015

ER -

Stable matchings with ties, master preference lists, and matroid constraints

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this