Generalized roof duality and bisubmodular functions Journal Article

Author(s): Kolmogorov, Vladimir
Article Title: Generalized roof duality and bisubmodular functions
Affiliation IST Austria
Abstract: Consider a convex relaxation f̂ of a pseudo-Boolean function f. We say that the relaxation is totally half-integral if f̂(x) is a polyhedral function with half-integral extreme points x, and this property is preserved after adding an arbitrary combination of constraints of the form x i=x j, x i=1-x j, and x i=γ where γ∈{0,1,1/2} is a constant. A well-known example is the roof duality relaxation for quadratic pseudo-Boolean functions f. We argue that total half-integrality is a natural requirement for generalizations of roof duality to arbitrary pseudo-Boolean functions. Our contributions are as follows. First, we provide a complete characterization of totally half-integral relaxations f̂ by establishing a one-to-one correspondence with bisubmodular functions. Second, we give a new characterization of bisubmodular functions. Finally, we show some relationships between general totally half-integral relaxations and relaxations based on the roof duality. On the conceptual level, our results show that bisubmodular functions provide a natural generalization of the roof duality approach to higher-order terms. This can be viewed as a non-submodular analogue of the fact that submodular functions generalize the s-t minimum cut problem with non-negative weights to higher-order terms.
Keywords: Bisubmodularity; Pseudo-boolean optimization; Roof duality; Conceptual levels; Convex relaxation; Extreme points; Higher order; Minimum cut; Natural generalization; Pseudo-Boolean function; Submodular functions; Integral equations; Relaxation processes; Roofs
Journal Title: Discrete Applied Mathematics
Volume: 160
Issue 4-5
ISSN: 0166-218X
Publisher: Elsevier  
Date Published: 2012-03-01
Start Page: 416
End Page: 426
DOI: 10.1016/j.dam.2011.10.026
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work