The Expressive Power of Binary Submodular Functions

DOI10.1007/978-3-642-03816-7_63zbMath1250.68122OpenAlexW2111456086MaRDI QIDQ3182971

Stanislav Živný, Peter G. Jeavons, David A. Cohen

Publication date: 16 October 2009

Published in: Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03816-7_63

zbMATH Keywords

decomposition of submodular functionspseudo-Boolean optimisationsubmodular function minimisationMin-Cut

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (1)

A note on some collapse results of valued constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pseudo-Boolean optimization
• Submodular function minimization
• A faster strongly polynomial time algorithm for submodular function minimization
• Minimization of locally defined submodular functions by optimal soft arc consistency
• Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
• Recognition problems for special classes of polynomials in 0-1 variables
• Constraints, consistency and closure
• Submodular functions and electrical networks
• On the supermodular knapsack problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Perspectives of Monge properties in optimization
• Supermodular functions and the complexity of MAX CSP
• The complexity of soft constraint satisfaction
• Supermodular functions on finite lattices
• Submodular functions and optimization.
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Maximizing Non-monotone Submodular Functions
• The approximability of MAX CSP with fixed-value constraints
• An Algebraic Characterisation of Complexity for Valued Constraint
• Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction
• An analysis of approximations for maximizing submodular set functions—I
• Some Network Flow Problems Solved with Pseudo-Boolean Programming
• The Approximability of Three-valued MAX CSP
• A Selection Problem of Shared Fixed Costs and Network Flows
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: The Expressive Power of Binary Submodular Functions