Every 2-CSP allows nontrivial approximation

DOI10.1145/1060590.1060700MaRDI QIDQ5901103zbMATH OpenOpenAlexFDO

Authors Johan Hastad

Publication date 16 August 2010

Published in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1060590.1060700

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25) Semidefinite programming (90C22) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Every 2-CSP allows nontrivial approximation
• 2 CSPs all are approximable within a constant differential factor
• Towards sharp inapproximability for any 2-CSP
• Approximation of non-Boolean 2CSP
• Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP
• Approximation Algorithms for CSPs
• A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• An approximation trichotomy for Boolean \#CSP

Cited in

(6)

• On bounded occurrence constraint satisfaction
• 2 CSPs all are approximable within a constant differential factor
• Towards sharp inapproximability for any 2-CSP
• Approximability Distance in the Space of H-Colourability Problems
• Approximation of non-Boolean 2CSP
• Every 2-CSP allows nontrivial approximation

This page was built for publication: Every 2-CSP allows nontrivial approximation

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