Inapproximability results for bounded variants of optimization problems

Miroslav Chlebik, Janka Chlebikova

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 9594 for Max-3DM, and factor of 4847 for Max-4DM; in both cases the hardness result applies even to instances with exactly two occurrences of each element.
Original languageEnglish
Title of host publicationFundamentals of computation theory
Subtitle of host publication14th international symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003. proceedings
EditorsAndrzej Lingas, Bengt J. Nilsson
Place of PublicationBerlin
ISBN (Electronic)9783540450771
ISBN (Print)9783540405436
Publication statusPublished - 2003

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Dive into the research topics of 'Inapproximability results for bounded variants of optimization problems'. Together they form a unique fingerprint.

Cite this