Zurück zu den Preprints des Jahres 1997


1997-42

The Simplex Method for Submodular Function Minimization

by Girlich, E., Pisaruk, N.N..


Series: 1997-42, Preprints

MSC:
90C10 Integer programming

Abstract:
The primal simplex method is applied for solving the problem of
minimizing a submodular function. As far as we know this is the first
primal algorithm for the problem. In [2] and [11] the dual simplex
method was applied for solving the problem. Here we prove that the
both methods are finite. Computational experiments show that these
methods are the methods of choise for using in practice.

Keywords:
minimization, submodular function, simplex method