On quadratic threshold CSPs

zbMATH Open1283.68317MaRDI QIDQ5403036FDOQ5403036

Authors: Per Austrin, Siavosh Benabbas, Avner Magen 

Publication date: 25 March 2014

Full work available at URL: https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2117/0.html

Recommendations

• On quadratic threshold CSPs
• Proving weak approximability without algorithms
• Approximating linear threshold predicates
• Approximating linear threshold predicates
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

zbMATH Keywords

combinatorial optimizationapproximation algorithmsconstraint satisfaction problems

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cited In (6)

• Approximating linear threshold predicates
• Approximating linear threshold predicates
• Proving weak approximability without algorithms
• On quadratic threshold CSPs
• A threshold for a polynomial solution of \#2SAT
• On the approximation resistance of balanced linear threshold functions

This page was built for publication: On quadratic threshold CSPs

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