DIMACS TR: 2007-14

On Approximating Four Covering/Packing Problems With Applications to Bioinformatics

Authors: Mary Ashley, Tanya Berger-Wolf, Piotr Berman, Wanpracha Chaovalitwongse, Bhaskar DasGupta and Ming-Yang Kao


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; 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) 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. 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. In spite of the many pessimistic worst-case inapproximability results, we provide consolation to the practitioners by concluding that an implementation of a version of the combinatorial heuristic for the full sibling reconstruction reported in [Berger-Wolf et al, 2007] performs empirically well on two new biological datasets.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2007/2007-14.pdf
DIMACS Home Page