Recognition of a class of unimodular functions

DOI10.1016/0166-218X(90)90147-5MaRDI QIDQ2638932zbMATH OpenFDO

Authors Bruno Simeone, Dominique De Werra, Maurice Cochand

Publication date 1990

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(90)90147-5

zbMATH Keywords

extended graphpolynomial-time recognition algorithmpseudo-Boolean functionstotally unimodular matrix

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Linear programming (90C05) Boolean programming (90C09) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Unimodular functions
• Recognition problems for special classes of polynomials in 0-1 variables
• From Linear Separability to Unimodality: A Hierarchy of Pseudo-Boolean Functions
• scientific article; zbMATH DE number 4162661
• Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions

Cites work

• A Selection Problem of Shared Fixed Costs and Network Flows
• Dualization of regular Boolean functions
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3249560 (Why is no real title available?)
• Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
• On unimodular matrices
• Unimodular functions

Cited in

(8)

• Unimodular functions
• The worst case behavior of a greedy algorithm for a class of pseudo- Boolean functions
• Recognition problems for special classes of polynomials in 0-1 variables
• A lower bound for a constrained quadratic \(0\)-\(1\) minimization problem
• On univariate function identification problems
• Characterization and recognition of d.c. functions
• scientific article; zbMATH DE number 4162661 (Why is no real title available?)
• A pseudo-Boolean consensus approach to nonlinear 0-1 optimization

This page was built for publication: Recognition of a class of unimodular functions

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