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 (24)

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

This page was built for publication: Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions