Bioinformatics Research at the University of Waterloo

In this talk, 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 talk
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
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 the full siblings reconstruction
problems and our almost matching upper and lower bounds for the
maximum profit coverage problem answers questions posedby previous
researchers.