Zurück zu den Preprints des Jahres 1995


Special Submodular and Bisubmodular Functionsand Their Cones

by Höding, M..

Series: 1995-14, Preprints


ing the last few years submodularity has intensively been investigated in com-
binatorial optimization, because it frequently appears in combinatorial systems like
networks, graphs and polyhedra.
The polyhedral aspects of matroids lead to the concept of polymatroids which
can be generated by submodular functions. Because special generalized polyhedra
can be generated by the so-called bisubmodular functions as a generalization of
the ordinary submodular functions, these functions have recently become more and
more important. Bisubmodular functions characterize functions on polyhedra for
which an optimal solution with respect to a linear objective can be determined by
a generalized greedy technique. In this paper sets of submodular and bisubmodular
functions generating special polyhedra are investigated.