Timezone: »
Poster
Generalized roof duality and bisubmodular functions
Vladimir Kolmogorov
Consider a convex relaxation $\hat f$ of a pseudoboolean function $f$. We say that the relaxation is {\em totally halfintegral} if $\hat f(\bx)$ is a polyhedral function with halfintegral extreme points $\bx$, and this property is preserved after adding an arbitrary combination of constraints of the form $x_i=x_j$, $x_i=1x_j$, and $x_i=\gamma$ where $\gamma\in\{0,1,\frac{1}{2}\}$ is a constant. A wellknown example is the {\em roof duality} relaxation for quadratic pseudoboolean functions $f$. We argue that total halfintegrality is a natural requirement for generalizations of roof duality to arbitrary pseudoboolean functions.
Our contributions are as follows. First, we provide a complete characterization of totally halfintegral relaxations $\hat f$ by establishing a onetoone correspondence with {\em bisubmodular functions}. Second, we give a new characterization of bisubmodular functions. Finally, we show some relationships between general totally halfintegral relaxations and relaxations based on the roof duality.
Author Information
Vladimir Kolmogorov (University College London)
More from the Same Authors

2007 Oral: An Analysis of Convex Relaxations for MAP Estimation »
Pawan K Mudigonda · Vladimir Kolmogorov · Philip Torr 
2007 Poster: An Analysis of Convex Relaxations for MAP Estimation »
Pawan K Mudigonda · Vladimir Kolmogorov · Philip Torr