Generalized roof duality and bisubmodular functions

V. Kolmogorov, Discrete Applied Mathematics 160 (2012) 416–426.


Journal Article | Published | English
Department
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.
Publishing Year
Date Published
2012-03-01
Journal Title
Discrete Applied Mathematics
Volume
160
Issue
4-5
Page
416 - 426
IST-REx-ID

Cite this

Kolmogorov V. Generalized roof duality and bisubmodular functions. Discrete Applied Mathematics. 2012;160(4-5):416-426. doi:10.1016/j.dam.2011.10.026
Kolmogorov, V. (2012). Generalized roof duality and bisubmodular functions. Discrete Applied Mathematics, 160(4–5), 416–426. https://doi.org/10.1016/j.dam.2011.10.026
Kolmogorov, Vladimir. “Generalized Roof Duality and Bisubmodular Functions.” Discrete Applied Mathematics 160, no. 4–5 (2012): 416–26. https://doi.org/10.1016/j.dam.2011.10.026.
V. Kolmogorov, “Generalized roof duality and bisubmodular functions,” Discrete Applied Mathematics, vol. 160, no. 4–5, pp. 416–426, 2012.
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.” Discrete Applied Mathematics, vol. 160, no. 4–5, Elsevier, 2012, pp. 416–26, doi:10.1016/j.dam.2011.10.026.

Link(s) to Main File(s)
Access Level
OA Open Access
Material in IST:
Earlier Version

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1005.2305

Search this title in

Google Scholar