2026-07-23T06:21:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6659 2024-03-06T10:38:37Z ddc:004 open_access

Stable Matching with Evolving Preferences Kanade, Varun Leonardos, Nikos Magniez, Frédéric Stable Matching Dynamic Data 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Varun Kanade and Nikos Leonardos and Frédéric Magniez 2016 Is Part Of LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2016.36 urn:nbn:de:0030-drops-66597 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.36 eng https://creativecommons.org/licenses/by/3.0/legalcode