Extensions of functions of 0-1 variables and applications to combinatorial optimization

From MaRDI portal





The author obtains some results on extensions of a pseudo-Boolean function f defined on the vertices of the 0-1 cube in \({\mathbb{R}}^ n\). The extension introduced is a piece-wise affine function, each of the n! pieces of which is the unique affine function, interpolating f on \(n+1\) affinely independent vertices of the cube. These vertices correspond to a given triangulation of the unit cube into simplices. Among other results, the proof is given that under a s.c. standard triangulation this extension coincides with the extension defined by Lovász. In the case of submodularity of f, the author proves that for its presentation \(\left( \begin{matrix} n\\ [n/2]\end{matrix} \right)\) unique affine functions suffice. As applications two duality theorems for minimization and maximization of submodular functions are proved.











This page was built for publication: Extensions of functions of 0-1 variables and applications to combinatorial optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3337950)