@inproceedings{b6cd2b1f508544e2a9d42dcb98ca0e15,

title = "Inapproximability results for bounded variants of optimization problems",

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 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.",

author = "Miroslav Chlebik and Janka Chlebikova",

year = "2003",

doi = "10.1007/978-3-540-45077-1_4",

language = "English",

isbn = "9783540405436",

volume = "2751",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "27--38",

editor = "Lingas, {Andrzej } and Nilsson, {Bengt J.}",

booktitle = "Fundamentals of computation theory",

}