Conference item
Stable matching with evolving preferences
- Abstract:
-
We consider the problem of stable matching with dynamic preference lists. At each time-step, the preference list of some player may change by swapping random adjacent members. The goal of a central agency (algorithm) is to maintain an approximately stable matching, in terms of number of blocking pairs, at all time-steps. The changes in the preference lists are not reported to the algorithm, but must instead be probed explicitly. We design an algorithm that in expectation and with high probability maintains a matching that has at most O((log n)2) blocking pairs.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 507.6KB, Terms of use)
-
- Publisher copy:
- 10.4230/LIPIcs.APPROX-RANDOM.2016.36
Authors
- Publisher:
- Schloss Dagstuhl
- Host title:
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
- Journal:
- LIPICS More from this journal
- Volume:
- 60
- Pages:
- 36:1--36:13
- Series:
- Leibniz International Proceedings in Informatics (LIPIcs)
- Publication date:
- 2016-09-01
- Acceptance date:
- 2016-06-22
- DOI:
- ISSN:
-
1868-8969
- ISBN:
- 9783959770187
- Keywords:
- Pubs id:
-
pubs:632973
- UUID:
-
uuid:b3927b91-0d43-414f-8395-1f4df689c469
- Local pid:
-
pubs:632973
- Source identifiers:
-
632973
- Deposit date:
-
2016-07-10
- ARK identifier:
Terms of use
- Copyright holder:
- Kanade et al
- Copyright date:
- 2016
- Notes:
-
Copyright © Varun Kanade, Nikos Leonardos, and Frédéric Magniez;
licensed under Creative Commons License CC-BY
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM
2016).
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record