Egyoldali párosítási piacok nehézségi eredményei magasabb dimenzióban

Hardness results of one-sided matching markets in higher dimensions

Gábor Kondor ()

Közgazdasági Szemle (Economic Review - monthly of the Hungarian Academy of Sciences), 2022, vol. LXIX, issue 7, 825-840

Abstract: Az egyoldali párosítási piacok tekintetében az irodalom nagyrészt kétfős párok létrehozását vizsgálja. A gyakorlati problémáknál - mint például a vese csere prog ra mok vagy a szobatársak beosztása - ugyanakkor előfordul, hogy háromfős vagy nagyobb csoportok létrehozása a feladat. A vesecserékre található olyan gyakorlati megoldás, amely súlyozott párosítási feladatra vezethető vissza. Ez alapján meghatározunk egy gráfparticionálási problémával ekvivalens megoldást, amelynek eredménye Pareto-hatékony. Megmutatjuk, hogy a felírt gráf particio ná lási és - ezek speciális eseteként - az egyenletes klaszterezési feladatok megoldása magasabb dimenzióban, vagyis legalább háromfős csoportok kialakítására általánosan NP-nehéz. A gyakorlatban ez azt jelenti, hogy bár biztosan tudjuk, hogy e problémákra létezik optimális megoldás, azt a résztvevők nagyobb száma esetén - jelen ismereteink szerint - képtelenek vagyunk meghatározni.* Journal of Economic Literature (JEL) kód: C78, D47.

JEL-codes: C78 D47 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.kszemle.hu/tartalom/letoltes.php?id=2061 (application/pdf)
Registration and subscription. 3-month embargo period to non-subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ksa:szemle:2061

Ordering information: This journal article can be ordered from
Közgazdasági Szemle Alapítvány (Economic Review Foundation) Budapest, Budaörsi út 45., 1112, Hungary
http://www.kszemle.hu/elofizetes/

DOI: 10.18414/KSZ.2022.7-8.825

Access Statistics for this article

Közgazdasági Szemle (Economic Review - monthly of the Hungarian Academy of Sciences) is currently edited by Tamás Halm

More articles in Közgazdasági Szemle (Economic Review - monthly of the Hungarian Academy of Sciences) from Közgazdasági Szemle Alapítvány (Economic Review Foundation)
Bibliographic data for series maintained by Odon Sok ( this e-mail address is bad, please contact ).