Complexity of approximating bounded variants of optimization problems

Miroslav Chlebik, Janka Chlebikova

Research output: Contribution to journalArticlepeer-review

208 Downloads (Pure)


We study low degree graph problems such as \textsc{Maximum
Independent Set} and \textsc{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 95/94 for Max-3-DM, and a factor of 48/47 for Max-4-DM. In both cases the hardness result applies even to instances with exactly two occurrences of each element.
Original languageEnglish
Pages (from-to)320-338
JournalTheoretical Computer Science
Issue number3
Publication statusPublished - 4 Apr 2006


Dive into the research topics of 'Complexity of approximating bounded variants of optimization problems'. Together they form a unique fingerprint.

Cite this