MTDP 2018/17
Ágnes Cseh – Jannik Matuschke
Új és egyszerű algoritmusok stabil folyamproblémákra / New and simple algorithms for stable flow problems
A stabil folyamprobléma a stabil párosításprobléma egy általánosítása olyan piacokra,
amelyeken számos játékos kooperál egymásnak folyamot küldve. A feladat egy inputja egy
kapacitással ellátott irányított hálózatból áll, amelyen minden játékos kifejezi a vele
szomszédos éleken vett szigorú preferenciáit. Egy hálózati folyam pontosan akkor stabil, ha
játékosok egyetlen csoportja sem tud megegyezni egyfajta változtatásban.
Fleiner bebizonyította, hogy stabil folyam mindig létezik a stabil allokációproblémára való
visszavezetéssel. Cikkünkben egy augmentáló út típusú algoritmussal számítunk ki egy stabil
folyamot, ami az első polinomiális algoritmus a stabil allokációs algoritmus használata
nélkül. Ezen felül tanulmányozzuk a tiltott és kötelező élek esetét, azaz amikor a
folyamértéknek egy megadott intervallumba kell esnie. A problémát egy elegáns
gráftranszformációval oldjuk meg, aminek segítségével egy gyors algoritmust tervezünk.
Végül a Király és Pap által bevezetett többtermékes folyamokat is vizsgáljuk. Az eredeti
modell igen bonyolult, amit gráfredukciókkal jelentősen mérsékelünk. Bebizonyítjuk azt is,
hogy az egészértékű megoldás találása NP-teljes probléma.
https://www.mtakti.hu/wp-content/uploads/2018/08/MTDP1817.pdf
Az MTA KRTK Közgazdaság-tudományi Intézet teljesítményéről Az MTA KRTK KTI a RePEc/IDEAS rangsorában, amely a világ közgazdaságtudományi tanszékeit és intézeteit rangsorolja publikációs teljesítményük alapján, ... Részletek »
Tisztelt Kollégák! Tudományos kutatóként, intézeti vezetőként egész életünkben a kutatói szabadság és felelősség elve vezetett bennünket. Meggyőződésünk, hogy a tudomány csak akkor érhet el ... Részletek »
Brokering the core and the periphery: Creative success and collaboration networks in the film industry Abstract In collaboration-based creative industries, such as film production, ... Részletek »
A távolságtartás elsőbbsége – M. Spence The Priority for the Social-Distancing Period Michael Spence Apr 1, 2020 – Project Syndicate Tesztelés és célzott izoláció ... Részletek »
Szerző: Hermann Zoltán Az iskolák bezárásával a magyar közoktatás egyik napról a másikra online távoktatási módszerekre állt át. Mindenki tudja, hogy vannak olyan diákok, ... Részletek »
