Files

Abstract

In a constraint satisfaction problem (CSP), we are given a set of variables and a set of constraints over these variables and the goal is to assign the variables so that as many constraints as possible are satisfied. Many problems in computer science can be phrased in this language so it is of great interest to either design efficient algorithms for this task or prove that such algorithms don't exist. In a breakthrough result, Raghavendra proved that for all CSPs there is a canonical semi-definite programming (SDP) relaxation that is optimal under the famous Unique Games Conjecture (UGC). More specifically, any integrality gap instances for this SDP relaxation can be turned into hardness results assuming UGC (or at least that unique games is hard) and there is a polynomial time rounding algorithm that achieves the integrality gap curve. However, this result does not tell us how to explicitly construct integrality gap instances for this SDP or what the optimal approximation ratio is for a given CSP. Moreover, the rounding algorithm has a doubly exponential dependency on the error parameter, which makes it practically infeasible. Based on Raghavendra's framework, we study the approximability for some classical CSPs, including MAX DI-CUT, MAX 2-SAT and its subproblems, and MAX NAE-SAT. In particular, assuming UGC (or at least that unique games is hard), we show that MAX DI-CUT is strictly harder to approximate than MAX CUT and MAX NAE-SAT does not have a 7/8-approximation algorithm. To do so, we construct explicit integrality gap instances for the canonical SDP relaxation for these problems. For MAX 2-SAT and its subproblems, we give tight approximability results (modulo UGC) by presenting matching approximation algorithms and unique games hardness results.

Details

Actions

PDF

from
to
Export
Download Full History