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 : Gáspár Attila – Corruption and Extremism

      2021.09.16.
      13:00 - 15:00

      Helyszín: Az előadást hibrid formában tartjuk meg : a személyes részvétel mellett (helyszín : KRTK Közgazdaságtudományi Intézet, 1097 Budapest, Tóth Kálmán u. 4., K11-K12 terem) zoomon keresztül is be lehet kapcsolódni. Az ehhez tartozó link külső érdeklődők számára a kti.titkarsag@krtk.hu e-mail címen igényelhető és csütörtök délután válik elérhetővé. előadó: Gáspár Attila társszerzők: Tommaso Giommoni Massimo Morelli Antonio Nicolò Abstract: This paper shows that corruption generates extremism, but almost exclusively on the opposition ...   Read More »

    • KTI szeminárium : Drucker Luca (CEU) -Meritocracy and Persistent Luck

      2021.09.30.
      09:00 - 11:00

      Helyszín: Az előadást hibrid formában tartjuk meg : a személyes részvétel mellett (helyszín : KRTK Közgazdaságtudományi Intézet, 1097 Budapest, Tóth Kálmán u. 4., K13-K14 terem) zoomon keresztül is be lehet kapcsolódni. Az ehhez tartozó link külső érdeklődők számára a kti.titkarsag@krtk.hu e-mail címen igényelhető és csütörtök délután válik elérhetővé. Abstract: In a meritocratic society inequality in economic outcomes that reflects differences in individual achievements is considered fair. However, a particular achievement is not equally ...   Read More »

    • KTI szeminárium : Győrfi Anita (Vienna Graduate School of Economics ) – Estimating gender differences in returns to elite schools

      2021.10.07.
      13:00 - 15:00

      Helyszín: Az előadást hibrid formában tartjuk meg : a személyes részvétel mellett (helyszín : KRTK Közgazdaságtudományi Intézet, 1097 Budapest, Tóth Kálmán u. 4., K11-K12 terem) zoomon keresztül is be lehet kapcsolódni. Az ehhez tartozó link külső érdeklődők számára a kti.titkarsag@krtk.hu e-mail címen igényelhető és csütörtök délután válik elérhetővé. Abstract: The paper examines gender differences in standardized test scores in an elite school environment by using Hungarian data. Raw test score averages suggest ...   Read More »

  • Hírek

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