| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 437130 | Theoretical Computer Science | 2006 | 19 Pages |
Abstract
We 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 for Max-3-DM, and a factor of for Max-4-DM. In both cases the hardness result applies even to instances with exactly two occurrences of each element.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
