Approximability of clausal constraints
From MaRDI portal
Publication:970111
DOI10.1007/s00224-008-9145-7zbMath1215.68216MaRDI QIDQ970111
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
computational complexity; constraint satisfaction; approximability; maximum solution; regular signed logic
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
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
