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

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 programok 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 particioná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.