On LP-based Approximability for Strict CSPs
Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth K. Vishnoi · 2011
In a beautiful result, Raghavendra established optimal Unique Games Conjecture (UGC)-based inapproximabil-ity for a large class of constraint satisfaction problems (CSPs). In the class of CSPs he considers, of which Maximum Cut is a prominent example, the goal is to find an assignment which maximizes a weighted fraction of constraints satisfied. He gave a generic semi-definite program (SDP) for this class of problems and showed how the approximability of each problem is determined by the corresponding SDP (upto an arbitrarily small ad-ditive error) assuming the UGC. He noted that his tech-niques do no apply to CSPs with strict constraints (all of which must be satisfied) such as Vertex Cover. In this paper we address the approximability of these strict-CSPs. In the class of CSPs we consider, one is given a set of constraints over a set of variables, and a cost function over the assignments, the goal is to find an assignment to the variables of minimum cost which satisfies all the constraints. We present a generic lin-ear program (LP) for a large class of strict-CSPs and give a systematic way to convert integrality gaps for this LP into UGC-based inapproximability results. Some im-portant problems whose approximability our framework captures are Vertex Cover, Hypergraph Vertex Cover, k-partite-Hypergraph Vertex Cover, Inde-pendent Set and other covering and packing problems over q-ary alphabets, and a scheduling problem. For the covering and packing problems, which occur quite com-monly in practice as well, we provide a matching round-ing algorithm, thus settling their approximability upto an arbitrarily small additive error.