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.
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
A KRTK Közgazdaság-tudományi Intézet teljesítményéről A KRTK KTI a RePEc/IDEAS rangsorában, amely a világ közgazdaság-tudományi tanszékeit és intézeteit rangsorolja publikációs teljesítményük alapján, a legjobb ... Read More »
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 ... Read More »
Srí Lanka: a 2022-es gazdasági válság leckéje – A. Krueger Lessons from Sri Lanka Anne O. Krueger Jul 25, 2022 – Project Syndicate ... Read More »
A permanens válság korában élünk – J. Meadway We’re living in an age of permanent crisis – let’s stop planning for a ‘return ... Read More »
A 2021 végén, illetve 2022 elején tapaszalt 6, illetve 7%-os cserearányromlás brutális reáljövedelem-kivonást jelentett a magyar gazdaságból. A külső egyensúly alakulásával foglalkozó elemzések többnyire ... Read More »
