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 HTK 1097 Budapest Tóth Kálmán u. 4. fszt. K011-12-es előadóterem Inequality is rising where social network segregation interacts with urban topology Gergő Tóth, Johannes Wachs, Riccardo Di Clemente, Ákos Jakobi, Bence Ságvári, János Kertész ... Details »
Venue: Budapest, Fővám tér 8. 1093 The Financial Research Centre, Department of Finance, Corvinus Business School, Corvinus University of Budapest and the Game Theory Research Group, Centre for Economic and Regional Studies, ... Details »
Venue: MTA HTK 1097 Budapest Tóth Kálmán u. 4. fszt. K011-12-es előadóterem The Cost of Favouritism in Public Procurement Bruno Baránek Department of Economics, Princeton University Vítézslav Titl Faculty of Economics and Business, University of Leuven ... Details »
Trading Networks with Frictions by Tamás FLEINER, Ravi JAGADEESAN, Zsuzsanna JANKÓ and Alexander TEYTELBOYM was published in Econometrica. download article here Share this:FacebookLinkedInTwitter
“The multiplier effect of local food: the protocol of a systematic review” was presented by Imre FERTŐ at the EAAE (European Association of Agricultural ... Details »
“Agricultural soft budget constraints in new European Union member states” by Imre FERTŐ, Štefan Bojnec, József Fogarasi and Ants Hannes Viira was published in ... Details »