Inapproximability results for bounded variants of optimization problems

Chlebik, Miroslav and Chlebíková, Janka (2003) Inapproximability results for bounded variants of optimization problems. In: 14th International Symposium on Fundamentals of Computation Theory, MALMO, SWEDEN.

Full text not available from this repository.


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 95/94 for MAX-3DM, and factor of 48/47 for MAX-4DM; in both cases the hardness result applies even to instances with exactly two occurrences of each element.

Item Type: Conference or Workshop Item (Paper)
Schools and Departments: School of Mathematical and Physical Sciences > Mathematics
Depositing User: Miroslav Chlebik
Date Deposited: 06 Feb 2012 21:01
Last Modified: 11 Apr 2012 11:07
📧 Request an update