Approximability of clausal constraints

DOI10.1007/S00224-008-9145-7MaRDI QIDQ970111zbMATHOpenAlexFDO

Authors Peter Jonsson, Gustav Nordh

Publication date 10 May 2010

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-008-9145-7

zbMATH Keywords

computational complexityconstraint satisfactionapproximabilitymaximum solutionregular signed logic

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• MAX ONES Generalized to Larger Domains
• Approximability of Integer Programming with Generalised Constraints
• The approximability of MAX CSP with fixed-value constraints
• Introduction to the Maximum Solution Problem
• The approximability of constraint satisfaction problems

Cites work

• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 2207163 (Why is no real title available?)
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A threshold of ln n for approximating set cover
• A unified theory of structural tractability for constraint satisfaction problems
• Applications of a Planar Separator Theorem
• Approximation algorithms for NP-complete problems on planar graphs
• Automated Reasoning
• Building tractable disjunctive constraints
• Classifying the Complexity of Constraints Using Finite Algebras
• Closure properties of constraints
• Complexity classifications of Boolean constraint satisfaction problems
• Complexity of clausal constraints over chains
• Constraint Satisfaction Problems with Infinite Templates
• Linear degree extractors and the inapproximability of max clique and chromatic number
• MAX ONES Generalized to Larger Domains
• Mathematical Foundations of Computer Science 2005
• On the Structure of Polynomial Time Reducibility
• Principles and Practice of Constraint Programming – CP 2004
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• Some APX-completeness results for cubic graphs
• Structure preserving reductions among convex optimization problems
• The Maximum Solution Problem on Graphs
• The approximability of constraint satisfaction problems
• The complexity of acyclic conjunctive queries
• The complexity of counting homomorphisms seen from the other side
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The complexity of reconstructing trees from qualitative characters and subtrees
• Tractable constraints on ordered domains

Cited in

(8)

• Approximability of Integer Programming with Generalised Constraints
• Approximability of Bounded Occurrence Max Ones
• Approximability of the Maximum Solution Problem for Certain Families of Algebras
• Projecting CLP(\({\mathcal R}\)) constraints
• Complexity of clausal constraints over chains
• scientific article; zbMATH DE number 1507192 (Why is no real title available?)
• Schmidt and Pudlák’s Approaches to CLP
• MAX ONES Generalized to Larger Domains

This page was built for publication: Approximability of clausal constraints

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