Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP
Yuichi Yoshida · 2011
Raghavendra (STOC 2008) gave an elegant and surprising result: if Khot's Unique Games Conjecture (STOC 2002) is true, then for every constraint satisfaction problem (CSP), the best approximation ratio is attained by a certain simple semidefinite programming and a rounding scheme for it.