Minimization on submodular flows |
| |
Authors: | U Zimmermann |
| |
Institution: | Mathematisches Institut, Universität zu Köln, Weyertal 86–90, D5000 Köln 41, West Germany |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|