To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

Submodular flow

From Wikipedia, the free encyclopedia

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

  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, 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, MR 2114523
This page was last edited on 28 November 2023, at 22:55
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.