{"id":{"repo_id":"corvinus","oai_identifier":"oai:phd.lib.uni-corvinus.hu:1210"},"canonical_url":"https://search.dev.ndltd.org/etd/corvinus/oai:phd.lib.uni-corvinus.hu:1210","repository":{"repo_id":"corvinus","name":"Corvinus University of Budapest","base_url":"http://phd.lib.uni-corvinus.hu/cgi/oai2"},"display":{"title":"Egyoldali párosítási piacok egyenletes klaszterezési megközelítésben","abstract":"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 m-szobatárs probléma formális definícióját, majd összevetem a szobatárs problémákat elméleti és gyakorlati szempontból. A bonyolultságelméleti eredmények tükrében ezután a gyakorlati megoldhatóság felé fordulok. Ehhez elsősorban áttekintem azokat az egyenletes klaszterezési problémák során alkalmazott algoritmusokat, amelyek valamilyen garanciát adnak az általuk talált megengedett megoldás szuboptimalitására: az approximációs eljárásokat, valamint a kúp optimalizálást. Másodsorban pedig a gyakorlati alkalmazások során leggyakrabban tekintett megoldási módszerre, a heurisztikus eljárásokra térek rá. E során az algoritmusok széles körét tekintem, amelyhez két módon járultam hozzá. Egyrészt különböző heurisztikus eljárásokat fogalmaztam meg a hagyományos klaszterelemzéshez kapcsolódó módszerek által adott, nem feltétlen egyenlő elemszámú csoportok kiegyenlítésére. Másrészt pedig az egyszerű párok cseréjével operáló LCW algoritmus esetén megvizsgáltam a nagyobb méretű cserék lehetőségét, és megfogalmaztam három heurisztikus eljárást, amelyek kettes és hármas cserék segítségével keresik az optimumot. A bemutatott valamennyi heurisztikus eljárást valós adathalmazokat és szimulációkat is magába foglaló, széleskörű elemzés során vetettem össze. A felállított elemzési keret erőssége, hogy lehetővé teszi, hogy egyszerre tekintsük mind a minimum-, mind a maximumfeladatot, és átfogóan elemezzük az m-szobatárs probléma gyakorlati megoldhatóságát. Ezekkel pedig túlmutatok a korábbi tanulmányokon, amelyek jellemzően az algoritmusok egy szűkebb körét és csupán az egyik célfüggvény ellenében tesztelik. A vizsgálathoz megadtam az összes szobabeosztás előállításának egy olyan konstrukcióját, amely lehetővé tette, hogy alacsony hallgatói számok mellett, az össztávolságokat hisztogramon ábrázolva szemügyre vegyük a megengedett megoldások terét. Az algoritmus felírásához a szobabeosztások formális definícióját is megadtam. További lényeges részlet az optimalitási pontszám definiálása, amelyet az elemzési keret minimum- és maximumproblémát is tartalmazó sajátosságát felhasználva tudtam bevezetni. Ennek segítségével ábrázoltam az algoritmusok egymáshoz képest vett teljesítményét, és a tesztelt heurisztikák alkalmazásával elérhető maximum- és minimumértékek különbségéhez képest is ki tudtam értékelni az algoritmusokat. A heurisztikus eljárások elemzése során a következő eredményeket fogalmazom meg. Az irodalomban hagyományosan tekintett, való életből származó ‘Iris’ és ‘Seeds’adathalmazokon a legtöbb minimalizáló eljárás hasonlóan jól teljesít, így nem lehet ez alapján különbséget tenni közöttük. Az egyszerű konstruktív módszerek, valamint a klaszterközéppontok meghatározását és az elemek klaszterközéppontokhoz való hozzárendelését alternáló eljárások nem teljesítenek jól a feladat megoldása során. A kis hallgatói létszámmal rendelkező esetek a szobabeosztások költségeinek ferde eloszlását mutatják, amely a minimalizálási és maximalizálási problémák lehetséges általános aszimmetriájára utal. A nagy hallgatói létszám esetén elvégzett elemzés megmutatja, hogy az optimalizálási problémák minimalizálási és maximalizálási feladat, valamint kis- és nagyméretű csoportok esetén is más-más karakterisztikákkal rendelkeznek, amely a heurisztikus eljárások teljesítményeiben tükröződik. A minimalizálási feladat megoldásához szignifikánsan nagyobb futásidő szükséges. A hármas cseréket is megvalósító LCW alapú heurisztika bizonyos esetekben önmagában is releváns. Ugyanebben a módszerben kezdeti értékként alkalmazva valamely másik eljárás által adott megengedett megoldást, előbbi jelentősen javíthat azok célfüggvényértékén. A lokális keresést alkalmazó eljárások köréből a legegyszerűbbnek számító és egyben leggyorsabb LCW eljárás teljesítménye pedig nem sokkal marad el a szofisztikáltabb módszerek eredményeitől, így a gyakorlati alkalmazás esetén a konkrét céltól függően ezzel is elfogadható megoldáshoz juthatunk.","abstract_html":"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 m-szobatárs probléma formális definícióját, majd összevetem a szobatárs problémákat elméleti és gyakorlati szempontból. A bonyolultságelméleti eredmények tükrében ezután a gyakorlati megoldhatóság felé fordulok. Ehhez elsősorban áttekintem azokat az egyenletes klaszterezési problémák során alkalmazott algoritmusokat, amelyek valamilyen garanciát adnak az általuk talált megengedett megoldás szuboptimalitására: az approximációs eljárásokat, valamint a kúp optimalizálást. Másodsorban pedig a gyakorlati alkalmazások során leggyakrabban tekintett megoldási módszerre, a heurisztikus eljárásokra térek rá. E során az algoritmusok széles körét tekintem, amelyhez két módon járultam hozzá. Egyrészt különböző heurisztikus eljárásokat fogalmaztam meg a hagyományos klaszterelemzéshez kapcsolódó módszerek által adott, nem feltétlen egyenlő elemszámú csoportok kiegyenlítésére. Másrészt pedig az egyszerű párok cseréjével operáló LCW algoritmus esetén megvizsgáltam a nagyobb méretű cserék lehetőségét, és megfogalmaztam három heurisztikus eljárást, amelyek kettes és hármas cserék segítségével keresik az optimumot. A bemutatott valamennyi heurisztikus eljárást valós adathalmazokat és szimulációkat is magába foglaló, széleskörű elemzés során vetettem össze. A felállított elemzési keret erőssége, hogy lehetővé teszi, hogy egyszerre tekintsük mind a minimum-, mind a maximumfeladatot, és átfogóan elemezzük az m-szobatárs probléma gyakorlati megoldhatóságát. Ezekkel pedig túlmutatok a korábbi tanulmányokon, amelyek jellemzően az algoritmusok egy szűkebb körét és csupán az egyik célfüggvény ellenében tesztelik. A vizsgálathoz megadtam az összes szobabeosztás előállításának egy olyan konstrukcióját, amely lehetővé tette, hogy alacsony hallgatói számok mellett, az össztávolságokat hisztogramon ábrázolva szemügyre vegyük a megengedett megoldások terét. Az algoritmus felírásához a szobabeosztások formális definícióját is megadtam. További lényeges részlet az optimalitási pontszám definiálása, amelyet az elemzési keret minimum- és maximumproblémát is tartalmazó sajátosságát felhasználva tudtam bevezetni. Ennek segítségével ábrázoltam az algoritmusok egymáshoz képest vett teljesítményét, és a tesztelt heurisztikák alkalmazásával elérhető maximum- és minimumértékek különbségéhez képest is ki tudtam értékelni az algoritmusokat. A heurisztikus eljárások elemzése során a következő eredményeket fogalmazom meg. Az irodalomban hagyományosan tekintett, való életből származó ‘Iris’ és ‘Seeds’adathalmazokon a legtöbb minimalizáló eljárás hasonlóan jól teljesít, így nem lehet ez alapján különbséget tenni közöttük. Az egyszerű konstruktív módszerek, valamint a klaszterközéppontok meghatározását és az elemek klaszterközéppontokhoz való hozzárendelését alternáló eljárások nem teljesítenek jól a feladat megoldása során. A kis hallgatói létszámmal rendelkező esetek a szobabeosztások költségeinek ferde eloszlását mutatják, amely a minimalizálási és maximalizálási problémák lehetséges általános aszimmetriájára utal. A nagy hallgatói létszám esetén elvégzett elemzés megmutatja, hogy az optimalizálási problémák minimalizálási és maximalizálási feladat, valamint kis- és nagyméretű csoportok esetén is más-más karakterisztikákkal rendelkeznek, amely a heurisztikus eljárások teljesítményeiben tükröződik. A minimalizálási feladat megoldásához szignifikánsan nagyobb futásidő szükséges. A hármas cseréket is megvalósító LCW alapú heurisztika bizonyos esetekben önmagában is releváns. Ugyanebben a módszerben kezdeti értékként alkalmazva valamely másik eljárás által adott megengedett megoldást, előbbi jelentősen javíthat azok célfüggvényértékén. A lokális keresést alkalmazó eljárások köréből a legegyszerűbbnek számító és egyben leggyorsabb LCW eljárás teljesítménye pedig nem sokkal marad el a szofisztikáltabb módszerek eredményeitől, így a gyakorlati alkalmazás esetén a konkrét céltól függően ezzel is elfogadható megoldáshoz juthatunk.","abstract_has_math":false,"creators":["Kondor, Gábor"],"institution":"Budapesti Corvinus Egyetem","degree_name":"phd","degree_level":"doctoral","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-11","date_published":"2022-11","updated_at":"2026-07-24T01:49:42Z","subjects":["Matematika. Ökonometria","Közgazdasági elméletek"],"languages":["hu","en"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":null,"outbound_label":null,"outbound_source":null},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Kondor, Gábor"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-11-24"]},{"key":"dc:date.issued","label":"Date","values":["2022-11"]},{"key":"dc:publisher.department","label":"Dc Publisher Department","values":["Közgazdasági és Gazdaságinformatikai Doktori Iskola"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["Budapesti Corvinus Egyetem"]},{"key":"dc:relation.isreferencedby","label":"Dc Relation Isreferencedby","values":["https://phd.lib.uni-corvinus.hu/1210/"]},{"key":"dc:relation.isreferencedby.uri","label":"Dc Relation Isreferencedby URI","values":["https://doi.org/10.14267/phd.2022071"]},{"key":"dc:type","label":"Dc Type","values":["Disszertáció"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["doctoral"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["phd"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Matematika. Ökonometria","Közgazdasági elméletek"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["hu","en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://phd.lib.uni-corvinus.hu/1210/1/Kondor_Gabor_dhu.pdf","https://phd.lib.uni-corvinus.hu/1210/2/Kondor_Gabor_thu.pdf","https://phd.lib.uni-corvinus.hu/1210/3/Kondor_Gabor_ten.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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 m-szobatárs probléma formális definícióját, majd összevetem a szobatárs problémákat elméleti és gyakorlati szempontból. A bonyolultságelméleti eredmények tükrében ezután a gyakorlati megoldhatóság felé fordulok. Ehhez elsősorban áttekintem azokat az egyenletes klaszterezési problémák során alkalmazott algoritmusokat, amelyek valamilyen garanciát adnak az általuk talált megengedett megoldás szuboptimalitására: az approximációs eljárásokat, valamint a kúp optimalizálást. Másodsorban pedig a gyakorlati alkalmazások során leggyakrabban tekintett megoldási módszerre, a heurisztikus eljárásokra térek rá. E során az algoritmusok széles körét tekintem, amelyhez két módon járultam hozzá. Egyrészt különböző heurisztikus eljárásokat fogalmaztam meg a hagyományos klaszterelemzéshez kapcsolódó módszerek által adott, nem feltétlen egyenlő elemszámú csoportok kiegyenlítésére. Másrészt pedig az egyszerű párok cseréjével operáló LCW algoritmus esetén megvizsgáltam a nagyobb méretű cserék lehetőségét, és megfogalmaztam három heurisztikus eljárást, amelyek kettes és hármas cserék segítségével keresik az optimumot. A bemutatott valamennyi heurisztikus eljárást valós adathalmazokat és szimulációkat is magába foglaló, széleskörű elemzés során vetettem össze. A felállított elemzési keret erőssége, hogy lehetővé teszi, hogy egyszerre tekintsük mind a minimum-, mind a maximumfeladatot, és átfogóan elemezzük az m-szobatárs probléma gyakorlati megoldhatóságát. Ezekkel pedig túlmutatok a korábbi tanulmányokon, amelyek jellemzően az algoritmusok egy szűkebb körét és csupán az egyik célfüggvény ellenében tesztelik. A vizsgálathoz megadtam az összes szobabeosztás előállításának egy olyan konstrukcióját, amely lehetővé tette, hogy alacsony hallgatói számok mellett, az össztávolságokat hisztogramon ábrázolva szemügyre vegyük a megengedett megoldások terét. Az algoritmus felírásához a szobabeosztások formális definícióját is megadtam. További lényeges részlet az optimalitási pontszám definiálása, amelyet az elemzési keret minimum- és maximumproblémát is tartalmazó sajátosságát felhasználva tudtam bevezetni. Ennek segítségével ábrázoltam az algoritmusok egymáshoz képest vett teljesítményét, és a tesztelt heurisztikák alkalmazásával elérhető maximum- és minimumértékek különbségéhez képest is ki tudtam értékelni az algoritmusokat. A heurisztikus eljárások elemzése során a következő eredményeket fogalmazom meg. Az irodalomban hagyományosan tekintett, való életből származó ‘Iris’ és ‘Seeds’adathalmazokon a legtöbb minimalizáló eljárás hasonlóan jól teljesít, így nem lehet ez alapján különbséget tenni közöttük. Az egyszerű konstruktív módszerek, valamint a klaszterközéppontok meghatározását és az elemek klaszterközéppontokhoz való hozzárendelését alternáló eljárások nem teljesítenek jól a feladat megoldása során. A kis hallgatói létszámmal rendelkező esetek a szobabeosztások költségeinek ferde eloszlását mutatják, amely a minimalizálási és maximalizálási problémák lehetséges általános aszimmetriájára utal. A nagy hallgatói létszám esetén elvégzett elemzés megmutatja, hogy az optimalizálási problémák minimalizálási és maximalizálási feladat, valamint kis- és nagyméretű csoportok esetén is más-más karakterisztikákkal rendelkeznek, amely a heurisztikus eljárások teljesítményeiben tükröződik. A minimalizálási feladat megoldásához szignifikánsan nagyobb futásidő szükséges. A hármas cseréket is megvalósító LCW alapú heurisztika bizonyos esetekben önmagában is releváns. Ugyanebben a módszerben kezdeti értékként alkalmazva valamely másik eljárás által adott megengedett megoldást, előbbi jelentősen javíthat azok célfüggvényértékén. A lokális keresést alkalmazó eljárások köréből a legegyszerűbbnek számító és egyben leggyorsabb LCW eljárás teljesítménye pedig nem sokkal marad el a szofisztikáltabb módszerek eredményeitől, így a gyakorlati alkalmazás esetén a konkrét céltól függően ezzel is elfogadható megoldáshoz juthatunk."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Egyoldali párosítási piacok egyenletes klaszterezési megközelítésben"]}]}],"canonical_facts":{"dc:creator":["Kondor, Gábor"],"dc:date":["2022-11-24"],"dc:date.issued":["2022-11"],"dc:description.abstract":["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 m-szobatárs probléma formális definícióját, majd összevetem a szobatárs problémákat elméleti és gyakorlati szempontból. A bonyolultságelméleti eredmények tükrében ezután a gyakorlati megoldhatóság felé fordulok. Ehhez elsősorban áttekintem azokat az egyenletes klaszterezési problémák során alkalmazott algoritmusokat, amelyek valamilyen garanciát adnak az általuk talált megengedett megoldás szuboptimalitására: az approximációs eljárásokat, valamint a kúp optimalizálást. Másodsorban pedig a gyakorlati alkalmazások során leggyakrabban tekintett megoldási módszerre, a heurisztikus eljárásokra térek rá. E során az algoritmusok széles körét tekintem, amelyhez két módon járultam hozzá. Egyrészt különböző heurisztikus eljárásokat fogalmaztam meg a hagyományos klaszterelemzéshez kapcsolódó módszerek által adott, nem feltétlen egyenlő elemszámú csoportok kiegyenlítésére. Másrészt pedig az egyszerű párok cseréjével operáló LCW algoritmus esetén megvizsgáltam a nagyobb méretű cserék lehetőségét, és megfogalmaztam három heurisztikus eljárást, amelyek kettes és hármas cserék segítségével keresik az optimumot. A bemutatott valamennyi heurisztikus eljárást valós adathalmazokat és szimulációkat is magába foglaló, széleskörű elemzés során vetettem össze. A felállított elemzési keret erőssége, hogy lehetővé teszi, hogy egyszerre tekintsük mind a minimum-, mind a maximumfeladatot, és átfogóan elemezzük az m-szobatárs probléma gyakorlati megoldhatóságát. Ezekkel pedig túlmutatok a korábbi tanulmányokon, amelyek jellemzően az algoritmusok egy szűkebb körét és csupán az egyik célfüggvény ellenében tesztelik. A vizsgálathoz megadtam az összes szobabeosztás előállításának egy olyan konstrukcióját, amely lehetővé tette, hogy alacsony hallgatói számok mellett, az össztávolságokat hisztogramon ábrázolva szemügyre vegyük a megengedett megoldások terét. Az algoritmus felírásához a szobabeosztások formális definícióját is megadtam. További lényeges részlet az optimalitási pontszám definiálása, amelyet az elemzési keret minimum- és maximumproblémát is tartalmazó sajátosságát felhasználva tudtam bevezetni. Ennek segítségével ábrázoltam az algoritmusok egymáshoz képest vett teljesítményét, és a tesztelt heurisztikák alkalmazásával elérhető maximum- és minimumértékek különbségéhez képest is ki tudtam értékelni az algoritmusokat. A heurisztikus eljárások elemzése során a következő eredményeket fogalmazom meg. Az irodalomban hagyományosan tekintett, való életből származó ‘Iris’ és ‘Seeds’adathalmazokon a legtöbb minimalizáló eljárás hasonlóan jól teljesít, így nem lehet ez alapján különbséget tenni közöttük. Az egyszerű konstruktív módszerek, valamint a klaszterközéppontok meghatározását és az elemek klaszterközéppontokhoz való hozzárendelését alternáló eljárások nem teljesítenek jól a feladat megoldása során. A kis hallgatói létszámmal rendelkező esetek a szobabeosztások költségeinek ferde eloszlását mutatják, amely a minimalizálási és maximalizálási problémák lehetséges általános aszimmetriájára utal. A nagy hallgatói létszám esetén elvégzett elemzés megmutatja, hogy az optimalizálási problémák minimalizálási és maximalizálási feladat, valamint kis- és nagyméretű csoportok esetén is más-más karakterisztikákkal rendelkeznek, amely a heurisztikus eljárások teljesítményeiben tükröződik. A minimalizálási feladat megoldásához szignifikánsan nagyobb futásidő szükséges. A hármas cseréket is megvalósító LCW alapú heurisztika bizonyos esetekben önmagában is releváns. Ugyanebben a módszerben kezdeti értékként alkalmazva valamely másik eljárás által adott megengedett megoldást, előbbi jelentősen javíthat azok célfüggvényértékén. A lokális keresést alkalmazó eljárások köréből a legegyszerűbbnek számító és egyben leggyorsabb LCW eljárás teljesítménye pedig nem sokkal marad el a szofisztikáltabb módszerek eredményeitől, így a gyakorlati alkalmazás esetén a konkrét céltól függően ezzel is elfogadható megoldáshoz juthatunk."],"dc:format":["application/pdf"],"dc:identifier.uri":["https://phd.lib.uni-corvinus.hu/1210/1/Kondor_Gabor_dhu.pdf","https://phd.lib.uni-corvinus.hu/1210/2/Kondor_Gabor_thu.pdf","https://phd.lib.uni-corvinus.hu/1210/3/Kondor_Gabor_ten.pdf"],"dc:language":["hu","en"],"dc:publisher.department":["Közgazdasági és Gazdaságinformatikai Doktori Iskola"],"dc:publisher.institution":["Budapesti Corvinus Egyetem"],"dc:relation.isreferencedby":["https://phd.lib.uni-corvinus.hu/1210/"],"dc:relation.isreferencedby.uri":["https://doi.org/10.14267/phd.2022071"],"dc:subject":["Matematika. Ökonometria","Közgazdasági elméletek"],"dc:title":["Egyoldali párosítási piacok egyenletes klaszterezési megközelítésben"],"dc:type":["Disszertáció"],"dc:type.qualificationlevel":["doctoral"],"dc:type.qualificationname":["phd"]},"updated_at":"2026-07-24T01:49:42Z"}