|
This paper examines the Balanced Submodular Flow Problem, that is the problem of finding a feasible submodular flow minimizing the difference between the flow values along the edges. A min-max formula is given to the problem and an algorithm is presented to solve it using $O(m^2)$ submodular function minimizations. Then, these result are extended to the weighted version of the problem. Finally, the Balanced Integer Submodular Flow Problem is discussed.
Bibtex entry:
| AUTHOR | = | {Jüttner, Alp{\'a}r and Szab{\'o}, Eszter}, |
| TITLE | = | {Balanced Submodular Flows}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2023}, |
| NUMBER | = | {TR-2023-09} |