97-42
The Simplex Method for Submodular Function Minimization
Preprint series: 97-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
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.