On structures of bisubmodular polyhedra

A bisubmodular polyhedron is defined in terms of a so-called bisubmodular function on a familiy of ordered pairs of disjoint subsets of a finite set. We examine the structures of bisubmodular polyhedra in terms of signed poset and exchangeability graph. We give characterizations of boundedness and pointedness of bisubmodular polyhedra and also give a characterization of extreme points together with an O(n"2) algorithm for discerning whether a given point is an extreme point, where n is the cardinality of the underlying set. The algorithm also determines the signed poset structure associated with the given point if it is an extreme point. We examine the greedy algorithm over possibly unbounded bisubmodular polyhedra and show an optimality condition in terms of exchangeability graph. We also give characterizations of faces and their dimensions and provide the adjacency relation of extreme points in terms of the Hasse diagrams of the associated signed posets. Moreover, we investigate the connectivity and the decomposition into connected components. (orig.)Available from TIB Hannover: RN 4052(94821) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekSIGLEDEGerman