Every 2-CSP allows nontrivial approximation
type: Item
instance of: scholarly article
title: Every 2-CSP allows nontrivial approximation
zbMATH Open document ID: 1192.90135
DOI: 10.1145/1060590.1060700
author: Johan Hastad
published in: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing
publication date: 2010-08-16T00:00:00Z
Mathematics Subject Classification ID: 90C22
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68T20
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 5771389
MaRDI profile type: MaRDI publication profile
full work available at URL: https://doi.org/10.1145/1060590.1060700
OpenAlex ID: W2161737792
Recommended article: Every 2-CSP allows nontrivial approximation
Recommended article: 2 CSPs all are approximable within a constant differential factor
Recommended article: Towards Sharp Inapproximability for Any 2-CSP
Recommended article: Approximation of non-boolean 2CSP
Recommended article: Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP
Recommended article: Approximation Algorithms for CSPs
Recommended article: Q4633872
Recommended article: A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
Recommended article: An approximation trichotomy for Boolean \#CSP
description: scientific article; zbMATH DE number 5771389