CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Popular matchings with two-sided preferences and one-sided ties

Á. Cseh ; Chien-Chung Huang (Institutionen för data- och informationsteknik, Datavetenskap (Chalmers)) ; T. Kavitha
42nd International Colloquium on Automata, Languages and Programming, ICALP 2015; Kyoto; Japan; Lecture Notes in Computer Science (0302-9743). Vol. 9134 (2015), p. 367-379.
[Konferensbidrag, refereegranskat]

We are given a bipartite graph G = (A ∪ B, E) where each vertex has a preference list ranking its neighbors: in particular, every a ∈ A ranks its neighbors in a strict order of preference, whereas the preference lists of b ∈ B may contain ties. A matching M is popular if there is no matching M’ such that the number of vertices that prefer M’ to M exceeds the number that prefer M to M’. We show that the problem of deciding whether G admits a popular matching or not is NP-hard. This is the case even when every b ∈ B either has a strict preference list or puts all its neighbors into a single tie. In contrast, we show that the problem becomes polynomially solvable in the case when each b ∈ B puts all its neighbors into a single tie. That is, all neighbors of b are tied in b’s list and and b desires to be matched to any of them. Our main result is an O(n2) algorithm (where n = |A ∪ B|) for the popular matching problem in this model. Note that this model is quite different from the model where vertices in B have no preferences and do not care whether they are matched or not.

Denna post skapades 2016-01-05. Senast ändrad 2016-01-08.
CPL Pubid: 229765


Läs direkt!

Länk till annan sajt (kan kräva inloggning)