Approximability of clausal constraints

DOI10.1007/s00224-008-9145-7zbMath1215.68216OpenAlexW2080500557MaRDI QIDQ970111

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)

Cites Work

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

This page was built for publication: Approximability of clausal constraints