On Approximating Four Covering and Packing Problems

Details On Approximating Four Covering and Packing Problems On Approximating Four Covering and Packing Problems

2011-02-04

arxiv.org/abs/1102.1006v1

Journal of Computer and System Sciences, 75, 287-302, 2009

Computer Science

Computational Complexity

25 pages

Scientific paper

10.1016/j.jcss.2009.01.002

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 full-sibling 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; this is done by directly transforming the inapproximability gap of Haastad 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 approximability results on the full siblings reconstruction problems answers questions originally posed by Berger-Wolf et al. 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.

Affiliated with

Also associated with

No associations

Rating

On Approximating Four Covering and Packing Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Approximating Four Covering and Packing Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Approximating Four Covering and Packing Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-492328