Cseh Ágnes és szerzőtársai cikke a Theory of Computing Systems folyóiratban

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.

  • Események

    • Nyári Műhely 2019

      2019.08.22.
      2019.08.22.
      9:00 - 18:00

      Helyszín: MTA HTK 1097 Budapest Tóth Kálmán u. 4. fszt. K013-14-es előadóterem Intézetünk augusztus 22–én (csütörtökön) az alábbi programmal műhely–konferenciát tart: Moderátor: Vincze János (Corvinus és KTI) 9:10–9:15 Megnyitó   9:15–10:15 Horváth Hedvig (UC London) – ...   Részletek »

    • KTI szeminárium – Bokányi Eszter 09.12

      2019.09.12.
      2019.09.12.
      14:00 - 16:00

      Helyszín: MTA HTK 1097 Budapest Tóth Kálmán u. 4. fszt. K013-14-es előadóterem Ride-share matching algorithms generate income inequality Eszter Bokányi and Anikó Hannák Abstract Despite the potential of online sharing economy platforms such as Uber, Lyft, ...   Részletek »

    • KTI szeminárium – Kiss Hubert János 09.19.

      2019.09.19.
      2019.09.19.
      14:00 - 16:00

      Helyszín: MTA HTK 1097 Budapest Tóth Kálmán u. 4. fszt. K011-12-es előadóterem Kiss Hubert János: Coopetition in group contest https://www.mtakti.hu/wp-content/uploads/2019/05/MTDP1911.pdf Megosztás:FacebookLinkedinTwitter

  • Hírek

Felhasználási feltételek
Impresszum
Intézményünk országos és nemzetközi hálózati kapcsolatát az NIIF program biztosítja
Magyar Tudományos Akadémia Közgazdaság- és Regionális Tudományi Kutatóközpont Közgazdaság-tudományi Intézet
© Copyright 2017. Minden jog fenntartva.