Cseh Ágnes és Jannik Matuschke közös cikke az Algorithmica folyóiratban

Cseh Ágnes tudományos munkatárs és Jannik Matuschke közös cikke New and Simple Algorithms for Stable Flow Problems címmel megjelent online az Algorithmica folyóiratban.

Abstract

Stable flows generalize the well-known concept of stable matchings to markets in which transactions may involve several agents, forwarding flow from one to another. An instance of the problem consists of a capacitated directed network in which vertices express their preferences over their incident edges. A network flow is stable if there is no group of vertices that all could benefit from rerouting the flow along a walk. Fleiner (Algorithms 7:1–14, 2014) established that a stable flow always exists by reducing it to the stable allocation problem. We present an augmenting path algorithm for computing a stable flow, the first algorithm that achieves polynomial running time for this problem without using stable allocations as a black-box subroutine. We further consider the problem of finding a stable flow such that the flow value on every edge is within a given interval. For this problem, we present an elegant graph transformation and based on this, we devise a simple and fast algorithm, which also can be used to find a solution to the stable marriage problem with forced and forbidden edges. Finally, we study the stable multicommodity flow model introduced by Király and Pap (Algorithms 6:161–168, 2013). The original model is highly involved and allows for commodity-dependent preference lists at the vertices and commodity-specific edge capacities. We present several graph-based reductions that show equivalence to a significantly simpler model. We further show that it is NPNP-complete to decide whether an integral solution exists

  • Események

    • KTI szeminárium – Neszveda Gábor (Corvinus) – 2019. május 30.

      2019.05.30.
      2019.05.30.
      14:00 - 16:00

      Helyszín: MTA Humán Tudományok Kutatóháza, 1097 Budapest, Tóth Kálmán utca 4. földszinti K11-12. sz. előadóterem Neszveda Gábor (Corvinus) Aspiration Level, Probability of Success, and Stock Returns: An Empirical Test The probability of achieving the aspiration level, i.e., the probability ...   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. május 20.

      2019.05.20.

      Hogyan jött létre alacsony inflációs világunk – M. WolfHow our low inflation world was madeMartin WolfMay 7, 2019 – Financial Times    Miért van ...   Részletek »

    • Sass Magdolna előadása a Pécsi Tudományegyetemen

      2019.05.14.

      Sass Magdolna tudományos főmunkatárs Poszt-szocialista multinacionális vállalatok címmel tartott előadást a Pécsi Tudományegyetem, a Regionális Innováció- és Vállalkozáskutató Központ (Regional Innovation and Entrepreneurship Research ...   Részletek »

    • Lengyel Balázs a Fiatal Kutatók Akadémiájának alapító tagja

      2019.05.10.

      A Magyar Tudományos Akadémia Elnöksége 2019. március 21-i ülésén jóváhagyólag tudomásul vette a Fiatal Kutatók Akadémiája polgári jogi társulás létrejöttét. Lengyel Balázs tudományos főmunkatársat ...   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.