Name
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 times. The changes in the preference lists are not reported to the algorithm, but must instead be probed explicitly by the algorithm. We design an algorithm that in expectation and with high probability maintains a matching that has at most $O((log (n))^2)$ blocking pairs. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.4230/LIPIcs.APPROX-RANDOM.2016.36 | international workshop and international workshop on approximation, randomization, and combinatorial optimization. algorithms and techniques |
Field | DocType | Volume |
Stable roommates problem,Discrete mathematics,Swap (computer programming),Mathematical optimization,Theoretical computer science,Mathematics | Journal | abs/1509.01988 |
Citations | PageRank | References |
2 | 0.43 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Varun Kanade | 1 | 122 | 21.94 |
| Nikos Leonardos | 2 | 225 | 13.04 |
| Frédéric Magniez | 3 | 570 | 44.33 |