MT/DP ajánló: Új és egyszerű algoritmusok stabil folyamproblémákra

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

 

  • Események

    • Nyári Műhely 2019

      2019.08.22.
      2019.08.22.
      9:00 - 18:00

      Helyszín: MTA HTK 1097 Budapest Tóth Kálmán u. 4. fszt. K013-14-es előadóterem Intézetünk augusztus 22–én (csütörtökön) az alábbi programmal műhely–konferenciát tart: Moderátor: Vincze János (Corvinus és KTI) 9:10–9:15 Megnyitó   9:15–10:15 Horváth Hedvig (UC London) – ...   Részletek »

    • KTI szeminárium – Bokányi Eszter 09.12

      2019.09.12.
      2019.09.12.
      14:00 - 16:00

      Helyszín: MTA HTK 1097 Budapest Tóth Kálmán u. 4. fszt. K013-14-es előadóterem Ride-share matching algorithms generate income inequality Eszter Bokányi and Anikó Hannák Abstract Despite the potential of online sharing economy platforms such as Uber, Lyft, ...   Részletek »

    • KTI szeminárium – Kiss Hubert János 09.19.

      2019.09.19.
      2019.09.19.
      14:00 - 16:00

      Helyszín: MTA HTK 1097 Budapest Tóth Kálmán u. 4. fszt. K011-12-es előadóterem Kiss Hubert János: Coopetition in group contest https://www.mtakti.hu/wp-content/uploads/2019/05/MTDP1911.pdf Megosztás:FacebookLinkedinTwitter

  • Hírek

Felhasználási feltételek
Impresszum
Intézményünk országos és nemzetközi hálózati kapcsolatát az NIIF program biztosítja
Magyar Tudományos Akadémia Közgazdaság- és Regionális Tudományi Kutatóközpont Közgazdaság-tudományi Intézet
© Copyright 2017. Minden jog fenntartva.