Chlebík, Miroslav and Chlebíková, Janka (2006) Complexity of approximating bounded variants of optimization problems. Theoretical Computer Science, 354 (3). pp. 320-338. ISSN 0304-3975

Full text not available from this repository.

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, B3. 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.

Item Type:	Article
Schools and Departments:	School of Mathematical and Physical Sciences > Mathematics
Depositing User:	Miroslav Chlebik
Date Deposited:	06 Feb 2012 18:55
Last Modified:	03 Apr 2012 14:29
URI:	http://sro.sussex.ac.uk/id/eprint/18909

📧 Request an update