Cseh Ágnes tudományos munkatárs és szerzőtársai közös cikke The Stable Roommates Problem with Short Lists címmel megjelent a Theory of Computing Systems folyóirat 2019. januári számában.
Á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.
A KRTK Közgazdaság-tudományi Intézet teljesítményéről A KRTK KTI a RePEc/IDEAS rangsorában, amely a világ közgazdaság-tudományi tanszékeit és intézeteit rangsorolja publikációs teljesítményük alapján, a legjobb ... Részletek »
Tisztelt Kollégák! Tudományos kutatóként, intézeti vezetőként egész életünkben a kutatói szabadság és felelősség elve vezetett bennünket. Meggyőződésünk, hogy a tudomány csak akkor érhet el ... Részletek »
Az írás a Public Choice Kornai János munkásságával foglalkozó, jövőre megjelenő különszáma egyik cikke. A cikk online már az idén megjelent a folyóirat honlapján. ... Részletek »
th International Scientific Conference on Rural Development entitled ”Chances and Challenges for the European Rural Development (2021-2027)” Date: Thursday, 26 November, 2020 11.10 – ... Részletek »
Benedek Mártok PhD disszertációja elnyerte a brit OR Society éves díját. Gratulálunk! ⇒Tovább a The Operational Reserach Society oldalára Megosztás:FacebookLinkedinTwitter
