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.

http://www.mtakti.hu/wp-content/uploads/2018/08/MTDP1817.pdf

 

  • Események

    • KTI szeminárium – Békés Gábor 2019.02.21.

      2019.02.21.
      2019.02.21.
      14:00 - 16:00

      Helyszín: MTA HTK 1097 Budapest Tóth Kálmán u. 4. fszt. K0.13-14 Békés Gábor, Bisztray Márta: Területi egyensúly – a munkaerőpiac és az ingatlanárak kapcsolata Magyarországon  A dolgozat célja annak felderítése, hogy a területi egyensúlyi modell ...   Részletek »

    • KTI szeminárium – Simonovits András 02.28.

      2019.02.28.
      2019.02.28.
      14:00 - 16:00

      Helyszín: MTA HTK 1097 Budapest Tóth Kálmán u. 4. fszt. K0.11-12 Simonovits András: Hagymahántás közben: a rugalmas nyugdíjkorhatár modelljei Az öregedő társadalmak nyugdíjgondjainak megoldásában az egyik leghatékonyabb eszköz az átlagos nyugdíjkorhatár (az ún. korcentrum) emelése. Ehhez ...   Részletek »

    • KTI szeminárium – Cseh Ágnes 03.07.

      2019.03.07.
      2019.03.07.
      14:00 - 16:00

      Helyszín: MTA HTK 1097 Budapest Tóth Kálmán u. 4. fszt. K0.11-12 Cseh Ágnes: Organizing Time Banks: Lessons from Matching Markets társszerzők: T. Andersson, L. Ehlers, and A. Erlanson A time bank is a group of ...   Részletek »

  • Hírek

    • Az MTA KRTK Közgazdaság-tudományi Intézet teljesítményéről

      2018.09.12.

      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 »

    • MTA KRTK állásfoglalás

      2018.06.20.

      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 »

    • 2019. február 18.

      2019.02.18.

      Közgazdaságtan a neoliberalizmus után – S. Naidu, D. Rodrik, G. Zucman Economics After Neoliberalism SURESH NAIDU, DANI RODRIK, GABRIEL ZUCMAN Boston Review – February ...   Részletek »

    • 2019. február 11.

      2019.02.11.

      D. McCloskey interjúja – E. Wallach An Interview with Deidre McCloskey, Distinguished Professor Emerita of Economics and of History, UIC Eric Wallach February 10, ...   Részletek »

    • Az MTA KRTK Közalkalmazotti Tanácsának értesítése

      2019.02.10.

      Értesítés 2019. február 6-án az MTA KRTK Közalkalmazotti Tanácsa az MTA Közgazdaság- és Regionális Tudományi Kutatóközpont intézeteinek valamennyi közalkalmazottjára kiterjedő elektronikus szavazást kezdeményezett az ...   Részletek »

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.