article
Generalized roof duality and bisubmodular functions
published
yes
Vladimir
Kolmogorov
author 3D50B0BA-F248-11E8-B48F-1D18A9856A87
VlKo
department
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.
Elsevier2012
eng
Discrete Applied Mathematics
1005.230510.1016/j.dam.2011.10.026
1604-5416 - 426
https://research-explorer.app.ist.ac.at/record/2934
Kolmogorov, V. (2012). Generalized roof duality and bisubmodular functions. <i>Discrete Applied Mathematics</i>, <i>160</i>(4–5), 416–426. <a href="https://doi.org/10.1016/j.dam.2011.10.026">https://doi.org/10.1016/j.dam.2011.10.026</a>
V. Kolmogorov, Discrete Applied Mathematics 160 (2012) 416–426.
V. Kolmogorov, “Generalized roof duality and bisubmodular functions,” <i>Discrete Applied Mathematics</i>, vol. 160, no. 4–5, pp. 416–426, 2012.
Kolmogorov V. Generalized roof duality and bisubmodular functions. <i>Discrete Applied Mathematics</i>. 2012;160(4-5):416-426. doi:<a href="https://doi.org/10.1016/j.dam.2011.10.026">10.1016/j.dam.2011.10.026</a>
Kolmogorov, Vladimir. “Generalized Roof Duality and Bisubmodular Functions.” <i>Discrete Applied Mathematics</i> 160, no. 4–5 (2012): 416–26. <a href="https://doi.org/10.1016/j.dam.2011.10.026">https://doi.org/10.1016/j.dam.2011.10.026</a>.
Kolmogorov V. 2012. Generalized roof duality and bisubmodular functions. Discrete Applied Mathematics. 160(4–5), 416–426.
Kolmogorov, Vladimir. “Generalized Roof Duality and Bisubmodular Functions.” <i>Discrete Applied Mathematics</i>, vol. 160, no. 4–5, Elsevier, 2012, pp. 416–26, doi:<a href="https://doi.org/10.1016/j.dam.2011.10.026">10.1016/j.dam.2011.10.026</a>.
32572018-12-11T12:02:18Z2020-01-21T11:48:31Z