On approximating four covering and packing problems (Q1021577): Difference between revisions

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.

0 references

Mathematics Subject Classification ID

90C27

0 references

0 references

0 references

covering and packing problems

0 references

sibling reconstruction in wild population

0 references

triangle packing

0 references

approximation hardness

0 references

reviewed by

Semen S. Kutateladze

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/j.jcss.2009.01.002

0 references

OpenAlex ID

W1895166666

0 references

cites work

A simulated annealing algorithm for maximum likelihood pedigree reconstruction

0 references

Derandomized graph products

0 references

Genome Rearrangements and Sorting by Reversals

0 references

Q2708231

0 references

Q4471294

0 references

On the complexity of approximating the independent set problem

0 references

Packing triangles in bounded degree graphs.

0 references

Set covering approach for reconstruction of sibling relationships

0 references

Complexity of approximating bounded variants of optimization problems

0 references

A threshold of ln n for approximating set cover

0 references

Zero knowledge and the chromatic number

0 references

The dense \(k\)-subgraph problem

0 references

Q4232775

0 references

A Maximum Profit Coverage Algorithm with Application to Small Molecules Cluster Identification

0 references

Q4526964

0 references

On the complexity of approximating \(k\)-set packing

0 references

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

0 references

The budgeted maximum coverage problem

0 references

Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1021577

@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.jcss.2009.01.002
+Normal rank
@@ Property / OpenAlex ID @@
+W1895166666
@@ Property / OpenAlex ID: W1895166666 / rank @@
+Normal rank
@@ Property / cites work @@
+A simulated annealing algorithm for maximum likelihood pedigree reconstruction
+Normal rank
@@ Property / cites work @@
+Derandomized graph products
@@ Property / cites work: Derandomized graph products / rank @@
+Normal rank
@@ Property / cites work @@
+Genome Rearrangements and Sorting by Reversals
@@ Property / cites work: Genome Rearrangements and Sorting by Reversals / rank @@
+Normal rank
@@ Property / cites work @@
+Q2708231
@@ Property / cites work: Q2708231 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4471294
@@ Property / cites work: Q4471294 / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of approximating the independent set problem
+Normal rank
@@ Property / cites work @@
+Packing triangles in bounded degree graphs.
@@ Property / cites work: Packing triangles in bounded degree graphs. / rank @@
+Normal rank
@@ Property / cites work @@
+Set covering approach for reconstruction of sibling relationships
+Normal rank
@@ Property / cites work @@
+Complexity of approximating bounded variants of optimization problems
+Normal rank
@@ Property / cites work @@
+A threshold of ln             <i>n</i>             for approximating set cover
+Normal rank
@@ Property / cites work @@
+Zero knowledge and the chromatic number
@@ Property / cites work: Zero knowledge and the chromatic number / rank @@
+Normal rank
@@ Property / cites work @@
+The dense \(k\)-subgraph problem
@@ Property / cites work: The dense \(k\)-subgraph problem / rank @@
+Normal rank
@@ Property / cites work @@
+Q4232775
@@ Property / cites work: Q4232775 / rank @@
+Normal rank
@@ Property / cites work @@
+A Maximum Profit Coverage Algorithm with Application to Small Molecules Cluster Identification
+Normal rank
@@ Property / cites work @@
+Q4526964
@@ Property / cites work: Q4526964 / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of approximating \(k\)-set packing
+Normal rank
@@ Property / cites work @@
+On the Size of Systems of Sets Every <i>t</i> of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
+Normal rank
@@ Property / cites work @@
+The budgeted maximum coverage problem
@@ Property / cites work: The budgeted maximum coverage problem / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for metric facility location and             <i>k</i>             -Median problems using the primal-dual schema and Lagrangian relaxation
+Normal rank