95-14
Special Submodular and Bisubmodular Functionsand Their Cones
by Höding, M.
Preprint series: 95-14, Preprints
Abstract: During the last few years submodularity has intensively been investigated in com-binatorial optimization, because it frequently appears in combinatorial systems likenetworks, graphs and polyhedra.The polyhedral aspects of matroids lead to the concept of polymatroids whichcan be generated by submodular functions. Because special generalized polyhedracan be generated by the so-called bisubmodular functions as a generalization ofthe ordinary submodular functions, these functions have recently become more andmore important. Bisubmodular functions characterize functions on polyhedra forwhich an optimal solution with respect to a linear objective can be determined bya generalized greedy technique. In this paper sets of submodular and bisubmodularfunctions generating special polyhedra are investigated.2