Supermodular functions and the complexity of MAX CSP

DOI10.1016/j.dam.2005.03.003zbMath1146.68378OpenAlexW2111739159MaRDI QIDQ2387428

Peter G. Jeavons, Martin C. Cooper, David A. Cohen, Andrei A. Krokhin

Publication date: 2 September 2005

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

Full work available at URL: https://doi.org/10.1016/j.dam.2005.03.003

zbMATH Keywords

ComplexityOptimizationSupermodularityConstraint satisfaction problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

The Complexity of General-Valued CSPs ⋮ Hard constraint satisfaction problems have hard gaps at location 1 ⋮ The Expressive Power of Binary Submodular Functions ⋮ Minimizing submodular functions on diamonds via generalized fractional matroid matchings ⋮ Classes of submodular constraints expressible by graph cuts ⋮ Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights ⋮ The Complexity of Valued CSPs ⋮ Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms ⋮ On the complexity of submodular function minimisation on diamonds ⋮ The expressive power of binary submodular functions ⋮ Minimization of locally defined submodular functions by optimal soft arc consistency

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• A dichotomy theorem for maximum generalized satisfiability problems.
• A combinatorial algorithm for MAX CSP
• Optimization, approximation, and complexity classes
• Submodular functions and optimization
• Geometric algorithms and combinatorial optimization
• On the algebraic structure of combinatorial problems
• Recognition of \(d\)-dimensional Monge arrays
• Submodular functions and electrical networks
• Minimization of an M-convex function
• Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights
• The approximability of non-Boolean satisfiability problems and restricted integer programming
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Minimizing submodular functions over families of sets
• Perspectives of Monge properties in optimization
• The Approximability of Constraint Satisfaction Problems
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Is constraint satisfaction over two variables always easy?
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• A new approach to the maximum-flow problem
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Minimizing a Submodular Function on a Lattice
• The Complexity of Multiterminal Cuts
• The Nonapproximability of Non-Boolean Predicates
• Computer Science Logic
• The complexity of satisfiability problems
• Some optimal inapproximability results

This page was built for publication: Supermodular functions and the complexity of MAX CSP