Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > APPROXIMATION LOWER BOUND:
Reports tagged with approximation lower bound:
TR03-026 | 20th February 2003
Janka Chlebíková, Miroslav Chlebík

Inapproximability results for bounded variants of optimization problems

We study small degree graph problems such as Maximum Independent Set
and Minimum Node Cover and improve approximation lower bounds for
them and for a number of related problems, like Max-B-Set Packing,
Min-B-Set Cover, Max-Matching in B-uniform 2-regular hypergraphs.
For example, we prove NP-hardness factor of 95/94
more >>>




ISSN 1433-8092 | Imprint