On approximating four covering and packing problems
From MaRDI portal
Publication:1021577
DOI10.1016/j.jcss.2009.01.002zbMath1169.90017MaRDI QIDQ1021577
Ming-Yang Kao, Piotr Berman, Wanpracha Art Chaovalitwongse, Bhaskar Das Gupta, Tanya Y. Berger-Wolf, Mary V. Ashley
Publication date: 8 June 2009
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2009.01.002
triangle packing; approximation hardness; covering and packing problems; sibling reconstruction in wild population
Related Items
AN IMPLICIT COVER PROBLEM IN WILD POPULATION STUDY, On Approximating an Implicit Cover Problem in Biology
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A simulated annealing algorithm for maximum likelihood pedigree reconstruction
- On the complexity of approximating the independent set problem
- Zero knowledge and the chromatic number
- The budgeted maximum coverage problem
- Derandomized graph products
- Packing triangles in bounded degree graphs.
- Complexity of approximating bounded variants of optimization problems
- On the complexity of approximating \(k\)-set packing
- A threshold of ln n for approximating set cover
- 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
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Genome Rearrangements and Sorting by Reversals
- A Maximum Profit Coverage Algorithm with Application to Small Molecules Cluster Identification
- Set covering approach for reconstruction of sibling relationships
- The dense \(k\)-subgraph problem
