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

edit
  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
  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
  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, ISBN 0-8186-4370-6, S2CID 32162097
  4. ^ 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, ISBN 1-58113-184-4, MR 2114523

📚 Artikel Terkait di Wikipedia

Linear programming

well-known integral LPs include the matching polytope, lattice polyhedra, submodular flow polyhedra, and the intersection of two generalized polymatroids/g-polymatroids

Feedback arc set

Gabow, Harold N. (1993), "A framework for cost-scaling algorithms for submodular flow problems", 34th Annual Symposium on Foundations of Computer Science

Jack Edmonds

graphs from the point of view of matchings. He introduced polymatroids, submodular flows with Richard Giles, and the terms clutter and blocker in the study

Dijoin

graph can be found in polynomial time, and is a special case of the submodular flow problem. In planar graphs, dijoins and feedback arc sets are dual concepts

Dual graph

MR 1857074. Gabow, Harold N. (1995), "Centroids, representations, and submodular flows", Journal of Algorithms, 18 (3): 586–628, doi:10.1006/jagm.1995.1022

Automatic summarization

submodular optimization. For example, the set cover problem is a special case of submodular optimization, since the set cover function is submodular.

Greedy algorithm

solution at least half the value of the optimal solution. Solutions for submodular maximization are approximated using a greedy algorithm which yields a

Graph cut optimization

function with a similar but submodular one, for instance truncating all non-submodular terms or replacing them with similar submodular expressions. Such approach