Unimodular functions

DOI10.1016/0166-218X(86)90031-4zbMath0597.90058OpenAlexW2912730163MaRDI QIDQ1079493

Bruno Simeone, Pierre Hansen

Publication date: 1986

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

Full work available at URL: https://doi.org/10.1016/0166-218x(86)90031-4

zbMATH Keywords

polynomial recognition algorithmunimodularpseudo-Boolean functionsmaximal flowcompletely unimodulartotal unimodilarityunate

Mathematics Subject Classification ID

Circuits, networks (94C99) Boolean programming (90C09)

Related Items

On dependent randomized rounding algorithms, A unified approach to polynomially solvable cases of integer ``non-separable quadratic optimization, Recognition of a class of unimodular functions, A lower bound for a constrained quadratic \(0\)-\(1\) minimization problem, Strong unimodularity for matrices and hypergraphs, Iterative Auction Design for Tree Valuations, On a class of functions attaining their maximum at the vertices of a polyhedron, Recognition problems for special classes of polynomials in 0-1 variables, Selecting a discrete portfolio, Solving the parametric bipartite maximum flow problem in unbalanced and closure bipartite graphs, A new?old algorithm for minimum-cut and maximum-flow in closure graphs, Berge-acyclic multilinear 0-1 optimization problems, A pseudo-Boolean consensus approach to nonlinear 0-1 optimization, Concave extensions for nonlinear 0-1 maximization problems, Complexity and algorithms for nonlinear optimization problems, Pseudo-Boolean optimization, The basic algorithm for pseudo-Boolean programming revisited, Computational complexity of norm-maximization, On dependent randomized rounding algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
• An \(O(IVI^3)\) algorithm for finding maximum flows in networks
• On unimodular matrices
• On the notion of balance of a signed graph
• Quasimonotone Boolean Functions and Bistellar Graphs
• Minimum cuts and related problems
• Maximal Closure of a Graph and Applications to Combinatorial Problems
• An analysis of approximations for maximizing submodular set functions—I
• `` Strong NP-Completeness Results
• A Selection Problem of Shared Fixed Costs and Network Flows
• Notes—On a Selection Problem