Supermodular functions and the complexity of MAX CSP

DOI10.1016/J.DAM.2005.03.003MaRDI QIDQ2387428zbMATH OpenOpenAlexFDO

Authors David A. Cohen, M. C. Cooper, P. Jeavons, Andrei 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

ComplexityConstraint satisfaction problemOptimizationSupermodularity

Mathematics Subject Classification ID

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

Recommendations

• STACS 2004
• Supermodularity on chains and complexity of maximum constraint satisfaction
• Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction
• Maximum Constraint Satisfaction on Diamonds
• The approximability of MAX CSP with fixed-value constraints

Cites work

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

Cited in

(21)

• Minimization of locally defined submodular functions by optimal soft arc consistency
• Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
• Minimizing submodular functions on diamonds via generalized fractional matroid matchings
• Log-supermodular functions, functional clones and counting CSPs
• A Survey on Covering Supermodular Functions
• The Expressive Power of Binary Submodular Functions
• The approximability of MAX CSP with fixed-value constraints
• Supermodularity on chains and complexity of maximum constraint satisfaction
• Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction
• scientific article; zbMATH DE number 4033805 (Why is no real title available?)
• The complexity of valued CSPs
• The complexity of general-valued CSPs
• STACS 2004
• Algorithms for maximization of supermodular functions and their application in the optimization of grouping provinces in a region
• Classes of submodular constraints expressible by graph cuts
• On the complexity of submodular function minimisation on diamonds
• Supermodularity in mean-partition problems
• Hard constraint satisfaction problems have hard gaps at location 1
• Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• The expressive power of binary submodular functions

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

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