2023/08/23 by Alpár Jüttner, Jüttner, Alpár, Eszter Szabó +1
Computer Science · Mathematics · #90C27 #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Flow (mathematics) #Function (biology) #Geometry #Integer (computer science) #Mathematical optimization #Mathematics #Maximum flow problem #Minimum-cost flow problem #Optimization and Control (math.OC) #Submodular set function
paper · pdf · doi:10.48550/arxiv.2308.12404
openalex publication_date 2023/08/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(m2) submodular function minimizations. Then, these result are extended to the weighted version of the problem. Finally, the Balanced Integer Submodular Flow Problem is discussed.