Special submodular and bisubmodular functions and their cones

During the last few years submodularity has intensively been investigated in combinatorial 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. (orig.)SIGLEAvailable from TIB Hannover: RR 4487(1995,14) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekDEGerman