submodular flow
{{Short description|Problem in combinatorial optimization}}
{{Use dmy dates|cs1-dates=ly|date=November 2022}}
{{Use list-defined references|date=November 2022}}
In the theory of combinatorial optimization, submodular flow is a general class of optimization problems that includes as special cases the minimum-cost flow problem, matroid intersection, and the problem of computing a minimum-weight dijoin in a weighted directed graph. It was originally formulated by Jack Edmonds and Rick Giles,{{r|eg}} and can be solved in polynomial time.{{r|gls|gabow|fi}}
In the classical minimum-cost flow problem, the input is a flow network, with given capacities that specify lower and upper limits on the amount of flow per edge, as well as costs per unit flow along each edge. The goal is to find a system of flow amounts that obey the capacities on each edge, obey Kirchhoff's law that the total amount of flow into each vertex equals the total amount of flow out, and have minimum total cost. In submodular flow, as well, one is given a submodular set function on sets of vertices of the graph. Instead of obeying Kirchhoff's law, it is a requirement that, for every vertex set, the excess flow (the function mapping the set to its difference between flow in and flow out) can be at most the value given by the submodular function.{{r|fi}}
References
{{reflist|refs=
| last1 = Edmonds | first1 = Jack | author1-link = Jack Edmonds
| last2 = Giles | first2 = Rick
| contribution = A min-max relation for submodular functions on graphs
| mr = 0460169
| pages = 185–204
| publisher = North-Holland, Amsterdam
| series = Annals of Discrete Mathematics
| title = Studies in integer programming (Proc. Workshop, Bonn, 1975)
| volume = 1
| year = 1977}}
| last1 = Fleischer | first1 = Lisa
| last2 = Iwata | first2 = Satoru
| contribution = Improved algorithms for submodular function minimization and submodular flow
| doi = 10.1145/335305.335318
| mr = 2114523
| pages = 107–116
| publisher = Association for Computing Machinery
| title = Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing
| year = 2000}}
| last = Gabow | first = Harold N. | author-link = Harold N. Gabow
| contribution = A framework for cost-scaling algorithms for submodular flow problems
| doi = 10.1109/SFCS.1993.366842
| pages = 449–458
| publisher = IEEE Computer Society
| title = Proceedings of the 34th Annual Symposium on Foundations of Computer Science (FOCS), Palo Alto, California, USA, 3-5 November 1993
| year = 1993| s2cid = 32162097 }}
| last1 = Grötschel | first1 = M.
| last2 = Lovász | first2 = L.
| last3 = Schrijver | first3 = A.
| doi = 10.1007/BF02579273
| issue = 2
| journal = Combinatorica
| mr = 625550
| pages = 169–197
| title = The ellipsoid method and its consequences in combinatorial optimization
| volume = 1
| year = 1981| s2cid = 43787103
}}
}}