Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions

DOI10.1016/0166-218X(85)90035-6zbMath0583.90067MaRDI QIDQ1069444

Michel Minoux, Alain Billionnet

Publication date: 1985

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

zbMATH Keywords

maximum flowconflict graphsupermodularmaximizing a pseudoboolean functionnegative-positive functions

Mathematics Subject Classification ID

Integer programming (90C10) Deterministic network models in operations research (90B10) Boolean programming (90C09)

Related Items

Unimodular functions, On a general framework for network representability in discrete optimization, The Expressive Power of Binary Submodular Functions, Recognition of a class of unimodular functions, A lower bound for a constrained quadratic \(0\)-\(1\) minimization problem, 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, Classes of submodular constraints expressible by graph cuts, A semantic relatedness preserved subset extraction method for language corpora based on pseudo-Boolean optimization, Directed acyclic graph continuous max-flow image segmentation for unconstrained label orderings, The Expressive Power of Valued Constraints: Hierarchies and Collapses, Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms, Efficient minimization of higher order submodular functions using monotonic Boolean functions, The expressive power of valued constraints: Hierarchies and collapses, The expressive power of binary submodular functions, Pseudo-Boolean optimization, Minimizing a sum of submodular functions, Generalized roof duality, An exact penalty function approach for nonlinear integer programming problems, Minimization of locally defined submodular functions by optimal soft arc consistency, On the supermodular knapsack problem, On a General Framework for Network Representability in Discrete Optimization, Polynomially Computable Bounds for the Probability of the Union of Events, A Polynomial Algorithm for a Class of 0–1 Fractional Programming Problems Involving Composite Functions, with an Application to Additive Clustering

Cites Work

• The ellipsoid method and its consequences in combinatorial optimization
• Comparaison expérimentale d'algorithmes pour les problèmes de recouvrement et de maximisation d'une fonction pseudo-booléenne
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Comments on F. Hadlock’s Paper: “Finding a Maximum Cut of a Planar Graph in Polynomial Time”
• An analysis of approximations for maximizing submodular set functions—I
• Paths, Trees, and Flowers
• A Selection Problem of Shared Fixed Costs and Network Flows
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item