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 Kiss Hubert János: Coopetition in group contest https://www.mtakti.hu/wp-content/uploads/2019/05/MTDP1911.pdf Share this:FacebookLinkedInTwitter
EUROPEAN UNION COUNTRIES AGRI-FOOD TRADE STRUCTURES AND MAIN COMPETITORS ON THE INTERNAL AND GLOBAL AGRI-FOOD MARKETS by Stefan BOJNEC and Imre FERTŐ was published ... Details »
Reduced user fees for antibiotics under age 5 in Hungary: Effect on antibiotic use and imbalances in the implementation by Anikó BÍRÓ was published ... Details »
Labor shares in the EU – sectoral effects and the role of relative prices was presented by Judit KREKÓ at the Conference on International ... Details »