New and Simple Algorithms for Stable Flow Problems by Ágnes CSEH and Jannik Matuschke was published online in Algorithmica.
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 -complete to decide whether an integral solution exists
Venue: 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 ... Details »
“Zero-rating and Net Neutrality” was presented by Róbert SOMOGYI at the 24th Spring Meeting of Young Economists in Brussels. conference website Share this:FacebookLinkedInTwitter
“Foreign-owned firms as agents of structural change in regions” by Zoltán ELEKES, Ron BOSCHMA and Balázs LENGYEL was published in Regional Studies. download open access version ... Details »
Wage Structure, Employment and Efficiency was presented by Balázs REIZER at the Royal Economic Society 2019 Annual Conference. conference website Abstract: I document new facts ... Details »