Complexity of approximating bounded variants of optimization problems

AbstractWe study low degree graph problems such as Maximum Independent Set and Minimum Vertex Cover. The goal is to improve approximation lower bounds for them and for a number of related problems like Max-B-Set Packing, Min-B-Set Cover, and Max-B-Dimensional Matching, B⩾3. We prove, for example, that it is NP-hard to achieve an approximation factor of 9594 for Max-3-DM, and a factor of 4847 for Max-4-DM. In both cases the hardness result applies even to instances with exactly two occurrences of each element