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 Citations (Scopus)

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

Covering Problem
Packing Problem
Inapproximability
Approximability
Profitability
Coverage
Profit
Triangle
Packing
Bioinformatics
Set Cover
Computational Biology
Genes
Annual
Biology
Upper and Lower Bounds
Genome
Molecules
Clustering
Optimization Problem

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
Ashley, Mary ; Berger-Wolf, Tanya ; Berman, Piotr ; Chaovalitwongse, Wanpracha ; DasGupta, Bhaskar ; Kao, Ming-Yang. / On approximating four covering and packing problems. In: Journal of Computer and System Sciences. 2009 ; Vol. 75, No. 5. pp. 287-302.
@article{9ece6ccea249449da05f518d31fdf6ee,
title = "On approximating four covering and packing problems",
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{\'i}kov{\'a}, M. Chleb{\'i}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{\aa}stad for the problem of maximizing the number of satisfied equations for a set of equations over GF(2) [J. H{\aa}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].",
keywords = "Approximation hardness, Covering and packing problems, Sibling reconstruction in wild population, Triangle packing",
author = "Mary Ashley and Tanya Berger-Wolf and Piotr Berman and Wanpracha Chaovalitwongse and Bhaskar DasGupta and Ming-Yang Kao",
year = "2009",
month = "8",
day = "1",
doi = "10.1016/j.jcss.2009.01.002",
language = "English (US)",
volume = "75",
pages = "287--302",
journal = "Journal of Computer and System Sciences",
issn = "0022-0000",
publisher = "Academic Press Inc.",
number = "5",

}

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, vol. 75, no. 5, pp. 287-302. https://doi.org/10.1016/j.jcss.2009.01.002

On approximating four covering and packing problems. / Ashley, Mary; Berger-Wolf, Tanya; Berman, Piotr; Chaovalitwongse, Wanpracha; DasGupta, Bhaskar; Kao, Ming-Yang.

In: Journal of Computer and System Sciences, Vol. 75, No. 5, 01.08.2009, p. 287-302.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On approximating four covering and packing problems

AU - Ashley, Mary

AU - Berger-Wolf, Tanya

AU - Berman, Piotr

AU - Chaovalitwongse, Wanpracha

AU - DasGupta, Bhaskar

AU - Kao, Ming-Yang

PY - 2009/8/1

Y1 - 2009/8/1

N2 - 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].

AB - 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].

KW - Approximation hardness

KW - Covering and packing problems

KW - Sibling reconstruction in wild population

KW - Triangle packing

UR - http://www.scopus.com/inward/record.url?scp=64449086025&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=64449086025&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2009.01.002

DO - 10.1016/j.jcss.2009.01.002

M3 - Article

AN - SCOPUS:64449086025

VL - 75

SP - 287

EP - 302

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

SN - 0022-0000

IS - 5

ER -

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