ECCC-Report TR09-124https://eccc.weizmann.ac.il/report/2009/124Comments and Revisions published for TR09-124en-usWed, 09 Dec 2009 07:39:13 +0200
Revision 1
| On the Optimality of a Class of LP-based Algorithms |
Amit Kumar,
Rajsekar Manokaran,
Madhur Tulsiani,
Nisheeth Vishnoi
https://eccc.weizmann.ac.il/report/2009/124#revision1In 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.
Wed, 09 Dec 2009 07:39:13 +0200https://eccc.weizmann.ac.il/report/2009/124#revision1
Paper TR09-124
| On the Optimality of a Class of LP-based Algorithms |
Amit Kumar,
Rajsekar Manokaran,
Madhur Tulsiani,
Nisheeth Vishnoi
https://eccc.weizmann.ac.il/report/2009/124In 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.
Tue, 24 Nov 2009 18:08:25 +0200https://eccc.weizmann.ac.il/report/2009/124