Edmonds-Giles theorem
From Egres Open
Let D=(V,A) be a digraph, and let b be a crossing submodular function on V. Let [math]f,g \in {\mathbb R}^A[/math] such that [math]f \leq g[/math].
Theorem (Edmonds and Giles [1]). The system [math]\max\{cx: f \leq x \leq g,\ \varrho_x(Z)-\delta_x(Z) \leq b(Z) \text{ for every }Z \subseteq V\}[/math] is totally dual integral.
A vector [math]x \in {\mathbb R}^A[/math] that satisfies the above inequalities is called a submodular flow. There are several different types of polynomial algorithms for deciding the existence of a submodular flow [2][3] and for finding a minimum cost submodular flow [4][5][6][7].
References
- ↑ J. Edmonds, R. Giles, A min-max relation for submodular functions on graphs, in: Studies in Integer Programming (Proceedings of the Workshop on Integer Programming, Bonn, 1975; P.L. Hammer, E.L. Johnson, B.H. Korte, G.L. Nemhauser, eds.), 1977, 185–204. DOI link, Google Books link.
- ↑ A. Frank, Finding feasible vectors of Edmonds-Giles polyhedra, DOI link, author link
- ↑ A. Frank, Z. Miklós, Push-relabel algorithms for matroids and submodular flows, DOI link, author link
- ↑ W.H. Cunningham, A. Frank, A primal-dual algorithm for submodular flows, DOI link, author link
- ↑ L. Fleischer, S. Iwata, S.T. McCormick, A faster capacity scaling algorithm for minimum cost submodular flow, DOI link, author link
- ↑ S. Iwata, S.T. McCormick, M. Shigeno, A fast cost scaling algorithm for submodular flow, DOI link, author link
- ↑ S. Iwata, S.T. McCormick, M. Shigeno, A strongly polynomial cut canceling algorithm for minimum cost submodular flow, DOI link, author link
