| On Approximating Four Covering and Packing Problems (2008) | |||||||||||||||
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 fullsibling 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 in [13, 16]; this is done by directly transforming the inapproximability gap of H˚astad for the problem of maximizing the number of satisfied equations for a set of equations over GF(2) [23] and is interesting in its own right. Our approximability results on the full siblings reconstruction problems answers questions posed by Berger-Wolf et al. [4, 5] 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 [22]. ∗ Supported by NSF grant IIS-0612044. † Supported by NSF grants DBI-0543365, IIS-0612044 and IIS-0346973. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||