Every 2-CSP allows nontrivial approximation

DOI10.1145/1060590.1060700zbMath1192.90135OpenAlexW2161737792MaRDI QIDQ5901103

Johan T. Håstad

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

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

Related Items (1)

Approximability Distance in the Space of H-Colourability Problems

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