Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with "vertex cover":
TR09-124 | 24th November 2009
Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth Vishnoi

On the Optimality of a Class of LP-based Algorithms

Revisions: 1

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
more >>>

ISSN 1433-8092 | Imprint