On structures of bisubmodular polyhedra

On structures of bisubmodular polyhedra

0.00 Avg rating0 Votes
Article ID: iaor1998330
Country: Netherlands
Volume: 74
Issue: 3
Start Page Number: 293
End Page Number: 317
Publication Date: Sep 1996
Journal: Mathematical Programming
Authors: ,
Keywords: posets, greedy algorithms
Abstract:

A bisubmodular polyhedron is defined in terms of a so-called bisubmodular function on a family 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 a characterization of extreme points together with an O(n2) algorithm for discerning whether a given point is an extreme point, where n is the cardinality of the underlying set, and we assume a function evaluation oracle for the bisubmodular function. The algorithm also determines the signed poset structure associated with the given point if it is an extreme point. We reveal the adjacency relation of extreme points by means of the Hasse diagrams of the associated signed posets. Moreover, we investigate the connectivity and the decomposition of a bisubmodular system into its connected components.

Reviews

Required fields are marked *. Your email address will not be published.