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
ABSTRACT
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