Revision #1 Authors: Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth Vishnoi

Accepted on: 9th December 2009 07:39

Downloads: 1438

Keywords:

In this paper we will be concerned with a large class of packing

and covering problems which includes Vertex Cover and Independent Set.

Typically, for NP-hard problems among them, one can write an LP relaxation and

then round the solution. For instance, for Vertex Cover, one can obtain a

2-approximation via this approach. On the other hand, Khot and Regev proved

that, assuming the Unique Games Conjecture (UGC), it is NP-hard to approximate

Vertex Cover to within a factor better than $2-\varepsilon$ for any constant

$\varepsilon>0$. From their, and subsequent proofs of this result, it was not clear

why this LP relaxation should be optimal.

The situation was akin to Maximum Cut, where a natural SDP relaxation for it

was proved by Khot et. al. to be optimal assuming the UGC. A beautiful result

of Raghavendra explains why the SDP is optimal (assuming the UGC). Moreover,

his result generalizes to a large class of constraint satisfaction

problems (CSPs). Unfortunately, we do not know how to extend his framework

so that it applies for problems such as Vertex Cover where the constraints

are strict.

In this paper, we explain why the simple {LP}-based rounding algorithm for

the Vertex Cover problem is optimal assuming the UGC. Complementing

Raghavendra's result, our result generalizes to a larger class of strict,

covering/packing type CSPs. We first write down a natural LP relaxation for

this class of problems and present a simple rounding algorithm for it. The

key ingredient, then, is a dictatorship test, which is parametrized by a

rounding-gap example for this LP, whose completeness and soundness are the

LP-value and the rounded value respectively. To the best of our knowledge,

ours is the first result which proves the optimality of LP-based rounding

algorithms systematically.

Added a section on extension of our results to q-ary alphabets.

TR09-124 Authors: Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth Vishnoi

Publication: 24th November 2009 18:08

Downloads: 1640

Keywords:

In this paper we will be concerned with a large class of packing

and covering problems which includes Vertex Cover and Independent Set.

Typically, for NP-hard problems among them, one can write an LP relaxation and

then round the solution. For instance, for Vertex Cover, one can obtain a

2-approximation via this approach. On the other hand, Khot and Regev proved

that, assuming the Unique Games Conjecture (UGC), it is NP-hard to approximate

Vertex Cover to within a factor better than $2-\varepsilon$ for any constant

$\varepsilon>0$. From their, and subsequent proofs of this result, it was not clear

why this LP relaxation should be optimal.

The situation was akin to Maximum Cut, where a natural SDP relaxation for it

was proved by Khot et. al. to be optimal assuming the UGC. A beautiful result

of Raghavendra explains why the SDP is optimal (assuming the UGC). Moreover,

his result generalizes to a large class of constraint satisfaction

problems (CSPs). Unfortunately, we do not know how to extend his framework

so that it applies for problems such as Vertex Cover where the constraints

are strict.

In this paper, we explain why the simple {LP}-based rounding algorithm for

the Vertex Cover problem is optimal assuming the UGC. Complementing

Raghavendra's result, our result generalizes to a larger class of strict,

covering/packing type CSPs. We first write down a natural LP relaxation for

this class of problems and present a simple rounding algorithm for it. The

key ingredient, then, is a dictatorship test, which is parametrized by a

rounding-gap example for this LP, whose completeness and soundness are the

LP-value and the rounded value respectively. To the best of our knowledge,

ours is the first result which proves the optimality of LP-based rounding

algorithms systematically.