Egyoldali párosítási piacok egyenletes klaszterezési megközelítésben

Az egyoldali párosítási piacokon nincs, vagy csak részben van olyan árrendszer, amely meghatározná az erőforrások allokációját. A létrejövő párosításokat elsősorban a piacot szabályozó mechanizmusok adják meg. Az egyoldali párosítási piacok egyik alkalmazási területére, a vesecsere-problémára létezik olyan megközelítés, amely egy súlyozott párosítási problémára vezet vissza. A disszertációban ezt a megközelítést általánosítom az m-dimenziós párosítások által, amelynek egy speciális esetét m-szobatárs problémaként definiáljuk. Ezzel egy Pareto-hatékony megközelítést határozunk meg, amelyben minimalizálási és maximalizálási problémákat is tekintünk. A megfogalmazott megoldási keretre egyenletes klaszterezési megközelítésként hivatkozunk, a disszertáció célja pedig ennek elméleti és gyakorlati megoldhatóságának vizsgálata. A megfogalmazott m-szobatárs problémában a hallgatókat euklideszi térbeli pontok reprezentálják, és azt hogy mennyire lennének egymás számára jó szobatársak, a közöttük adódó távolságok adják meg. A cél azonosan m fős szobák beosztása a szobákon belüli távolságnégyzetek összegének minimalizálása vagy maximalizálása mellett attól függően, hogy homogén vagy heterogén klasztereket kívánunk megadni. A dolgozatban elsőként összefoglalom az azonos elemszámú csoportok kialakításának és általánosan az elemszámkorlátokkal ellátott feladatok szakirodalomban előforduló széleskörű alkalmazási lehetőségeit. Ezt követően bevezetem a probléma nehézségének tárgyalásához elengedhetetlen fogalmakat, majd ezek ismeretében áttekintést adok a szakirodalomban található, az egyenletes klaszterezéshez kapcsolódó problémák bonyolultságelméleti eredményeiről. Az általános dimenziós eredményeket kiterjesztem, és megmutatom, hogy valamennyi általunk tekintett probléma legalább háromfős csoportok esetén NP-nehéz, vagyis jelenlegi ismereteink szerint nem tudjuk általánosan hatékonyan megoldani. Ezután bemutatom az egyoldali párosítások legalapvetőbb, stabil szobatársak megközelítésének fontosabb eredményeit, megadom az ...