Extensions of functions of 0-1 variables and applications to combinatorial optimization
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.
- A decomposition theorem for partially ordered sets
- A triangulation of the n-cube
- Convex Analysis
- Extension of Fenchel's duality theorem for convex functions
- Extreme convex set functions with finite carrier: General theory
- scientific article; zbMATH DE number 3887245 (Why is no real title available?)
- scientific article; zbMATH DE number 3534506 (Why is no real title available?)
- scientific article; zbMATH DE number 3249560 (Why is no real title available?)
- Maximization of lower semi-continuous convex functionals on bounded subsets of locally convex spaces. I: Hyperplane theorems
- On \Phi -Convexity in Extremal Problems
- Some new applications of the Fenchel-Rockafellar duality theorem: Lagrange multiplier theorems and hyperplane theorems for convex optimization and best approximation
- Theory of submodular programs: A Fenchel-type min-max theorem and subgradients of submodular functions
- Triangulations for the cube
- On the extension of pseudo-Boolean functions for the aggregation of interacting criteria.
- Approximations of Lovász extensions and their induced interaction index
- Axiomatizations of signed discrete Choquet integrals
- Fuzzy measures and integrals: recent developments
- Incompatible extensions of combinatorial functions
- Dualities between complete lattices
- Bipolar and bivariate models in multicriteria decision analysis: Descriptive and constructive approaches
- Axiomatizations of Lovász extensions of pseudo-Boolean functions
- The arity gap of order-preserving functions and extensions of pseudo-Boolean functions
- Generalized roof duality and bisubmodular functions
- Dual representation of cooperative games based on fenchel-moreau conjugation
- A complete classification of equational classes of threshold functions included in clones
- CAPACITIES AND GAMES ON LATTICES: A SURVEY OF RESULTS
- A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid
- A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid
- Axiomatizations of quasi-Lovász extensions of pseudo-Boolean functions
- Concave extensions for nonlinear 0-1 maximization problems
- Distribution functions of linear combinations of lattice polynomials from the uniform distribu\-tion
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)