Complexity of approximating bounded variants of optimization problems

Miroslav Chlebik, Janka Chlebikova

Research output: Contribution to journalArticlepeer-review

145 Downloads (Pure)

Abstract

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
Volume354
Issue number3
DOIs
Publication statusPublished - 4 Apr 2006

Fingerprint

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

Cite this