The Stable Roommates Problem with Short Lists by Ágnes CSEH et.al in Theory of Computing Systems:
Ágnes Cseh, Robert W. Irving, David F. Manlove: The Stable Roommates Problem with Short Lists
Abstract
We consider two variants of the classical Stable Roommates problem with Incomplete (but strictly ordered) preference lists (sri) that are degree constrained, i.e., preference lists are of bounded length. The first variant, egald-sri, involves finding an egalitarian stable matching in solvable instances of sri with preference lists of length at most d. We show that this problem is NP-hard even if d = 3. On the positive side we give a 2d+37 -approximation algorithm for d ∈{3,4,5} which improves on the known bound of 2 for the unbounded preference list case. In the second variant of sri, called d-srti, preference lists can include ties and are of length at most d. We show that the problem of deciding whether an instance of d-srti admits a stable matching is NP-complete even if d = 3. We also consider the “most stable” version of this problem and prove a strong inapproximability bound for the d = 3 case. However for d = 2 we show that the latter problem can be solved in polynomial time.
“PARENTAL JOB LOSS, SECONDARY SCHOOL COMPLETION AND HOME ENVIRONMENT” by Tamás HAJDU, Gábor KERTESI and Gábor KÉZDI was published in Acta Oeconomica. Abstract This ... Details »
Trading Networks with Frictions by Tamás FLEINER, Ravi JAGADEESAN, Zsuzsanna JANKÓ and Alexander TEYTELBOYM was published in Econometrica. download article here Share this:FacebookLinkedInTwitter
“The multiplier effect of local food: the protocol of a systematic review” was presented by Imre FERTŐ at the EAAE (European Association of Agricultural ... Details »
