On quadratic threshold CSPs

MaRDI QIDQ5403036zbMATH OpenFDO

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

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)

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

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)