96-23
On Complexity of Maximation of Submodular Functions
by Girlich, E.; Kovalev, M.; Moshchensky, A.
Preprint series: 96-23, Preprints
- MSC:
- 90C10 Integer programming
Abstract: We investigate the oracle complexity of the following two prob-lems. The first problem is to find all local maxima of a submodularfunction defined on lattice 2 N . The function is given by a proceduresgf-oracle which says: the function increases or decreases on an edgeof lattice 2 N . The objective is to minimize the number of sgf-oraclecalls. We derive an optimal algorithm for the case of lattice 2 N andfor the case of lattice Z n T[0; h]; h = (2; \Delta \Delta \Delta ; 2); n = 2k+1. The secondproblem is to find the global maximum of a submodular function de-fined on lattice 2 N . The function is given by f-oracle which computesthe function value. The objective is to minimize the number of f -oracle calls. We present a hybrid algorithm using sgf - and f-oracles.The (sgf + f)-complexity of the hybrid algorithm equals to the f -complexity of finding the global maximum of a submodular function,but the sgf-oracle is cheaper for some applications than the f-oracle.
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.