On the efficient approximability of constraint satisfaction problems

MaRDI QIDQ5421814zbMATH OpenFDO

Authors Johan Hastad

Publication date 24 October 2007

Mathematics Subject Classification ID

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

Recommendations

• On bounded occurrence constraint satisfaction
• scientific article; zbMATH DE number 6381632
• scientific article; zbMATH DE number 1002207
• The approximability of constraint satisfaction problems
• Every 2-CSP allows nontrivial approximation

Cited in

(20)

• Approximate Constraint Satisfaction Requires Large LP Relaxations
• Complexity of approximating CSP with balance / hard constraints
• An efficient algorithm for a class of constraint satisfaction problems
• On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Sparsification of SAT and CSP Problems via Tractable Extensions
• From weak to strong linear programming gaps for all constraint satisfaction problems
• Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
• Automata, Languages and Programming
• Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
• scientific article; zbMATH DE number 6381632 (Why is no real title available?)
• Pseudorandom sets in Grassmann graph have near-perfect expansion
• Near-optimal algorithms for maximum constraint satisfaction problems
• Adaptive Constraint Satisfaction: The Quickest First Principle
• On bounded occurrence constraint satisfaction
• On the complexity of trial and error for constraint satisfaction problems
• On approximability of satisfiable k -CSPs: I
• scientific article; zbMATH DE number 6783493 (Why is no real title available?)
• scientific article; zbMATH DE number 1303558 (Why is no real title available?)
• Fast and parallel decomposition of constraint satisfaction problems

This page was built for publication: On the efficient approximability of constraint satisfaction problems

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