On approximating four covering and packing problems

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

*Corresponding author for this work

Research output: Contribution to journalArticle

6 Scopus citations

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 in [A. Caprara, R. Rizzi, Packing triangles in bounded degree graphs, Inform. Process. Lett. 84 (4) (2002) 175-180; J. Chlebíková, M. Chlebík, Complexity of approximating bounded variants of optimization problems, Theoret. Comput. Sci. 354 (3) (2006) 320-338]; this is done by directly transforming the inapproximability gap of Håstad for the problem of maximizing the number of satisfied equations for a set of equations over GF(2) [J. Håstad, Some optimal inapproximability results, in: Proc. of the 29th Annual ACM Symp. on Theory of Computing, 1997, pp. 1-10] 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. [T.Y. Berger-Wolf, B. DasGupta, W. Chaovalitwongse, M.V. Ashley, Combinatorial reconstruction of sibling relationships, in: Proc. of the 6th International Symposium on Computational Biology and Genome Informatics, 2005, pp. 1252-1255; T.Y. Berger-Wolf, S. Sheikh, B. DasGupta, M.V. Ashley, I. Caballero, W. Chaovalitwongse, S.L. Putrevu, Reconstructing sibling relationships in wild populations, Bioinformatics 23 (13) (2007) i49-i56] 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 [R. Hassin, E. Or, A maximum profit coverage algorithm with application to small molecules cluster identification, in: 5th International Workshop Experimental Algorithms, in: Lecture Notes in Comput. Sci., vol. 4007, Springer-Verlag, 2006, pp. 265-276].

Original languageEnglish (US)
Pages (from-to)287-302
Number of pages16
JournalJournal of Computer and System Sciences
Volume75
Issue number5
DOIs
StatePublished - Aug 1 2009

    Fingerprint

Keywords

  • Approximation hardness
  • Covering and packing problems
  • Sibling reconstruction in wild population
  • Triangle packing

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Cite this

Ashley, M., Berger-Wolf, T., Berman, P., Chaovalitwongse, W., DasGupta, B., & Kao, M-Y. (2009). On approximating four covering and packing problems. Journal of Computer and System Sciences, 75(5), 287-302. https://doi.org/10.1016/j.jcss.2009.01.002