Abstract :
A set function image, is said to be polyhedrally tight (pt) (dually polyhedrally tight (dpt)) iff in the set polyhedron (dual set polyhedron) denoted by Pf (Pf) defined byimageevery inequality can be satisfied as an equality (not necessarily simultaneously).
We show that these are precisely the set functions that can be extended to convex (concave) functionals over image. We characterize such functions and show that if they have certain additional desirable properties, they are forced to become submodular/supermodular. We study pt and dpt functions using the notion of a legal dual generator (LDG) structure which is a refinement of the sets of generator vectors of the dual cones associated with the faces of the set polyhedron. We extend f(g) to convex and concave functionals on image byimage
We then show a refinement (in terms of LDG) of the following discrete separation theorem.
Theorem 0.1
If f is polyhedrally tight, g is dually polyhedrally tight and f greater-or-equal, slanted g and Pf and Pg have the same dual cones associated with their faces, then fcup greater-or-equal, slanted gcap and there exists a modular function h s.t. f greater-or-equal, slanted h greater-or-equal, slanted g.
We give sufficient conditions on the dual generator structures of f, g in order that h is integral when f, g are integral. Using these we derive the (integral) Sandwich Theorem for submodular/supermodular functions and (working with a (0, 1, −1) coefficient matrix generalization of set polyhedra), the 1/2-integral Sandwich Theorem for pseudomatroids. We also study the relative positions of Edmonds Intersection Theorem and Frank’s Sandwich Theorem in this class of set functions. It turns out that the former is difficult to generalize unless we generalize the definition of convolution while the latter is routinely generalizable to all pt/dpt functions. Using polyhedral ideas we show that if a set function satisfies the Sandwich Theorem with all supermodular functions it must be submodular.
