Minimization on submodular flows
Minimization on submodular flows
复制标题
子模流最小化
DOI：
10.1016/0166-218x(82)90053-1
复制
发表时间：
1982
期刊：
影响因子：
--
通讯作者：
Uwe Zimmermann
中科院分区：
文献类型：
--
作者：
Uwe Zimmermann
Edmonds和Giles [1]讨论了有向图的弧上满足子模集约束的函数。我们称这样的函数为次模流，证明了群值次模流的差是在某个辅助有向图中的网络循环，并给出了群值次模流存在的一个判据.我们开发了一种方法，用于最大化的值的组值的子模流在一个指定的弧和负电路的方法，用于最小化某些功能的环值的子模流。特别地，模和某些半模上的代数线性函数以及全序交换域上的线性函数的导数可以被最小化。
Edmonds and Giles [1] discuss functions on the arcs of a digraph satisfying submodular set constraints. We call such functions submodular flows, show that the difference of group-valued submodular flows is a network circulation in a certain auxiliary digraph, and derive a criterion for the existence of group-valued submodular flows. We develop a method for maximizing the value of a group-valued submodular flow in a specified arc and a negative circuit method for minimizing certain functions on ring-valued submodular flows. In particular, algebraic linear functions over modules and certain semimodules as well as quotients of linear functions over totally ordered, commutative fields can be minimized.