On approximating four covering and packing problems
type: Item
instance of: scholarly article
title: On approximating four covering and packing problems
zbMATH Open document ID: 1169.90017
author: Piotr Berman
author: Ming-Yang Kao
author: Mary V. Ashley
author: Tanya Y. Berger-Wolf
author: Wanpracha A. Chaovalitwongse
author: Bhaskar Dasgupta
published in: Journal of Computer and System Sciences
publication date: 2009-06-08T00:00:00Z
review text: This article deals with application of covering and packing problems to biology. The focus is on the triangle packing, full sibling reconstruction, maximum profit coverage and 3-coverage. The authors's inapproximability constant improves the earlier results, while the results on full siblings reconstruction problem answer questions by Berge-Wolf et. al. A few other relevant problems of bioinformatics are discussed.
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C90
zbMATH DE Number: 5562797
zbMATH Keywords: covering and packing problems
zbMATH Keywords: sibling reconstruction in wild population
zbMATH Keywords: triangle packing
zbMATH Keywords: approximation hardness
reviewed by: S. S. Kutateladze
MaRDI profile type: Publication
full work available at URL: j.jcss.2009.01.002
OpenAlex ID: W1895166666
cites work: A simulated annealing algorithm for maximum likelihood pedigree reconstruction
cites work: Derandomized graph products
cites work: Genome Rearrangements and Sorting by Reversals
cites work: A \(d/2\) approximation for maximum weight independent set in \(d\)-claw free graphs
cites work: Q4471294
cites work: On the complexity of approximating the independent set problem
cites work: Packing triangles in bounded degree graphs.
cites work: Set covering approach for reconstruction of sibling relationships
cites work: Complexity of approximating bounded variants of optimization problems
cites work: A threshold of ln n for approximating set cover
cites work: Zero knowledge and the chromatic number
cites work: The dense \(k\)-subgraph problem
cites work: Q4232775
cites work: A Maximum Profit Coverage Algorithm with Application to Small Molecules Cluster Identification
cites work: Q4526964
cites work: On the complexity of approximating \(k\)-set packing
cites work: On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
cites work: The budgeted maximum coverage problem
cites work: Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
DOI: 10.1016/J.JCSS.2009.01.002
description: scientific article; zbMATH DE number 5562797