On Approximating Four Covering/Packing Problems With Applications to Bioinformatics
Mary V. Ashley, Tanya Y. Berger-Wolf · 2007
In this paper, we consider approximability of four covering/packing type problems which have important applications in computational biology. The problems considered in this paper are the triangle packing problem, the full sibling reconstruction problem under two parsimonious assumptions, the maximum profit coverage problem and the 2-coverage problem. We provide approximation algorithms and inapproximability results for various values of parameters of interest for these problems. Our inapproximability constant for the triangle packing problem improves slightly upon the best-known inapproximability constant that can be achieved from previous results [14]; this is done by directly transforming the inapproximability gap of Hastad for the problem of maximizing the number of satisfied equations for a set of equations over GF(2) [26] and is interesting in its own right. Our inapproximability results on full siblings reconstruction problems answers open questions about the computational complexities of these problems posed by Berger-Wolf et al. [5]. Our results on the maximum profit coverage problem provides almost matching upper and lower bounds on the approximation ratios for this problem posed by Hassin and Or [25].