Generalized roof duality and bisubmodular functions
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(\bx)$ is a polyhedral function with half-integral extreme points $\bx$, 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,\frac{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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Distance Functions and Generalized Means: Duality and Taxonomy
This paper introduces in production theory a large class of efficiency measures that can be derived from the notion of utility function. This article also establishes a relation between these distance functions and Stone…
Conjugate Gradients and Accelerated Methods Unified: The Approximate Duality Gap View
This note provides a novel, simple analysis of the method of conjugate gradients for the minimization of convex quadratic functions. In contrast with standard arguments, our proof is entirely self-contained and does not …
Generalized Duality for Model-Free Superhedging given Marginals
In a discrete-time financial market, a generalized duality is established for model-free superhedging, given marginal distributions of the underlying asset. Contrary to prior studies, we do not require contingent claims …
modelOn the Taut String Interpretation of the One-dimensional Rudin-Osher-Fatemi Model: A New Proof, a Fundamental Estimate and Some Applications
A new proof of the equivalence of the Taut String Algorithm and the one-dimensional Rudin-Osher-Fatemi model is presented. Based on duality and the projection theorem in Hilbert space, the proof is strictly elementary. E…
DenoisingregressionA Short and General Duality Proof for Wasserstein Distributionally Robust Optimization
We present a general duality result for Wasserstein distributionally robust optimization that holds for any Kantorovich transport cost, measurable loss function, and nominal probability distribution. Assuming an intercha…