Approximability of clausal constraints

DOI10.1007/S00224-008-9145-7zbMATH Open1215.68216OpenAlexW2080500557MaRDI QIDQ970111FDOQ970111

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

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

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

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

Cited In (8)

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

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)