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.
|Title of host publication||Fundamentals of computation theory |
|Subtitle of host publication||14th international symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003. proceedings|
|Editors||Andrzej Lingas, Bengt J. Nilsson|
|Place of Publication||Berlin|
|Publication status||Published - 2003|
|Name||Lecture Notes in Computer Science|