by Girlich, E., Kovalev, M., Moshchensky, A..

**Series:** 1996-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 submodular

function defined on lattice 2 N . The function is given by a procedure

sgf-oracle which says: the function increases or decreases on an edge

of lattice 2 N . The objective is to minimize the number of sgf-oracle

calls. We derive an optimal algorithm for the case of lattice 2 N and

for the case of lattice Z n T

[0; h]; h = (2; \Delta \Delta \Delta ; 2); n = 2k+1. The second

problem is to find the global maximum of a submodular function de-

fined on lattice 2 N . The function is given by f-oracle which computes

the 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.

**Keywords:**