Submodular flow

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,^[1] and can be solved in polynomial time.^[2]^[3]^[4]

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.^[4]

References

^ Edmonds, Jack; Giles, Rick (1977), "A min-max relation for submodular functions on graphs", Studies in integer programming (Proc. Workshop, Bonn, 1975), Annals of Discrete Mathematics, vol. 1, North-Holland, Amsterdam, pp. 185–204, MR 0460169
^ Grötschel, M.; Lovász, L.; Schrijver, A. (1981), "The ellipsoid method and its consequences in combinatorial optimization", Combinatorica, 1 (2): 169–197, doi:10.1007/BF02579273, MR 0625550, S2CID 43787103
^ Gabow, Harold N. (1993), "A framework for cost-scaling algorithms for submodular flow problems", Proceedings of the 34th Annual Symposium on Foundations of Computer Science (FOCS), Palo Alto, California, USA, 3-5 November 1993, IEEE Computer Society, pp. 449–458, doi:10.1109/SFCS.1993.366842, S2CID 32162097
^ ^a ^b Fleischer, Lisa; Iwata, Satoru (2000), "Improved algorithms for submodular function minimization and submodular flow", Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 107–116, doi:10.1145/335305.335318, MR 2114523

[eg-1] Edmonds, Jack; Giles, Rick (1977), "A min-max relation for submodular functions on graphs", Studies in integer programming (Proc. Workshop, Bonn, 1975), Annals of Discrete Mathematics, vol. 1, North-Holland, Amsterdam, pp. 185–204, MR 0460169

[gls-2] Grötschel, M.; Lovász, L.; Schrijver, A. (1981), "The ellipsoid method and its consequences in combinatorial optimization", Combinatorica, 1 (2): 169–197, doi:10.1007/BF02579273, MR 0625550, S2CID 43787103

[gabow-3] Gabow, Harold N. (1993), "A framework for cost-scaling algorithms for submodular flow problems", Proceedings of the 34th Annual Symposium on Foundations of Computer Science (FOCS), Palo Alto, California, USA, 3-5 November 1993, IEEE Computer Society, pp. 449–458, doi:10.1109/SFCS.1993.366842, S2CID 32162097

[fi-4] Fleischer, Lisa; Iwata, Satoru (2000), "Improved algorithms for submodular function minimization and submodular flow", Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 107–116, doi:10.1145/335305.335318, MR 2114523

[1]

[2]

[3]

[4]