On Variants of Network Flow Stability

10/09/2017
by   Young-San Lin, et al.
0

We present a variant of the stable flow problem. Instead of the traditional flow problem that obeys Kirchhoff's law, for each vertex, the outflow is monotone and piecewise linear to the inflow. In a directed and capacitated network, each vertex has strict preference over their incident edges. A stable flow assignment does not allow a group of vertices to benefit from privately rerouting along a path. In this paper, we first show the existence of flow stability by reducing this variant of stable flow problem to Scarf's Lemma, then introduce a path augmenting algorithm that runs in polynomial time to find such a stable flow.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset