|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
27 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
On Approximating Four Covering and Packing Problems | | Mary Ashley
; Tanya Berger-Wolf
; Piotr Berman
; Wanpracha Chaovalitwongse
; Bhaskar DasGupta
; Ming-Yang Kao
; | | Date: |
4 Feb 2011 | | Abstract: | 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. | | Source: | arXiv, 1102.1006 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER