Computer Science – Discrete Mathematics
Scientific paper
2010-05-13
Computer Science
Discrete Mathematics
14 pages. Shorter version to appear in NIPS 2010
Scientific paper
Consider a convex relaxation $\hat f$ of a pseudo-boolean function $f$. We say that the relaxation is {\em totally half-integral} if $\hat 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=\gamma$ where $\gamma\in\{0, 1, 1/2}$ is a constant. A well-known example is the {\em 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 $\hat f$ by establishing a one-to-one correspondence with {\em 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.
No associations
LandOfFree
Generalized roof duality and bisubmodular functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Generalized roof duality and bisubmodular functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generalized roof duality and bisubmodular functions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-640581