Maximum Constraint Satisfaction on Diamonds

DOI10.1007/11564751_30MaRDI QIDQ3524191zbMATH OpenOpenAlexFDO

Authors Andrei Krokhin, Benoît Larose

Publication date 9 September 2008

Published in Principles and Practice of Constraint Programming - CP 2005 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11564751_30

Mathematics Subject Classification ID

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

Recommendations

• MAX-closed semilinear constraint satisfaction
• scientific article; zbMATH DE number 6381632
• Near-optimal algorithms for maximum constraint satisfaction problems
• On the Approximation of Maximum Satisfiability
• Full Constraint Satisfaction Problems
• Exact Max-SAT solvers for over-constrained problems
• Theory and Applications of Satisfiability Testing
• On Solving the Partial MAX-SAT Problem
• Quantified maximum satisfiability

Cited in

(8)

• Finitely repeated search and the diamond paradox
• Supermodular functions and the complexity of MAX CSP
• Supermodularity on chains and complexity of maximum constraint satisfaction
• Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction
• STACS 2004
• 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

This page was built for publication: Maximum Constraint Satisfaction on Diamonds

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