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

DOI10.1016/0166-218X(85)90035-6zbMATH Open0583.90067MaRDI QIDQ1069444FDOQ1069444

Alain Billionnet, Michel Minoux

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

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

Cites Work

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

Cited In (25)

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

   Recommendations

• Supermodular functions and the complexity of MAX CSP 👍 👎
• Title not available (Why is that?) 👍 👎
• Constrained Monotone Function Maximization and the Supermodular Degree 👍 👎
• Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction 👍 👎
• Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case 👍 👎
• Title not available (Why is that?) 👍 👎
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions 👍 👎
• Submodularity, Supermodularity, and Higher-Order Monotonicities of Pseudo-Boolean Functions 👍 👎
• Maximizing k -Submodular Functions and Beyond 👍 👎
• An approximation algorithm and its performance guarantee for minimizing non-decreasing supermodular set function 👍 👎

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

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