ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR03-026 | 20th February 2003 00:00

Inapproximability results for bounded variants of optimization problems

RSS-Feed

Abstract:

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
for Max-3-Dimensional Matching, and factor of 48/47 for
Max-4-Dimensional Matching; in both cases the hardness
result applies even to instances with exactly two occurrences of
each element.



ISSN 1433-8092 | Imprint