Zurück zu den Preprints des Jahres 1996


1996-23

On Complexity of Maximation of Submodular Functions

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: