On Approximating Four Covering and Packing Problems
Preprint
Abstract
In this paper, we consider approximability issues of the following four problems: triangle packing, full sibling reconstruction, maximum profit coverage and 2-coverage. All of them are generalized or specialized versions of set-cover and have applications in biology ranging from full-sibling reconstructions in wild populations to biomolecular clusterings; however, as this paper shows, their approximability properties differ considerably. Our inapproximability constant for the triangle packing problem improves upon the previous results; this is done by directly transforming the inapproximability gap of Haastad for the problem of maximizing the number of satisfied equations for a set of equations over GF(2) and is interesting in its own right. Our approximability results on the full siblings reconstruction problems answers questions originally posed by Berger-Wolf et al. and our results on the maximum profit coverage problem provides almost matching upper and lower bounds on the approximation ratio, answering a question posed by Hassin and Or.Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- On the complexity of approximating k-set packingcomputational complexity, 2006
- Complexity of approximating bounded variants of optimization problemsTheoretical Computer Science, 2005
- Approximation Hardness for Small Occurrence Instances of NP-Hard Problems2003
- Packing triangles in bounded degree graphsInformation Processing Letters, 2002
- A d/2 Approximation for Maximum Weight Independent Set in d-Claw Free GraphsLecture Notes in Computer Science, 2000
- The budgeted maximum coverage problemInformation Processing Letters, 1999
- Zero Knowledge and the Chromatic NumberJournal of Computer and System Sciences, 1998
- Derandomized graph productscomputational complexity, 1995
- On the complexity of approximating the independent set problemInformation and Computation, 1992
- Maximum bounded 3-dimensional matching is MAX SNP-completeInformation Processing Letters, 1991