On approximating four covering and packing problems

DOI10.1016/j.jcss.2009.01.002zbMath1169.90017OpenAlexW1895166666MaRDI QIDQ1021577

Ming-Yang Kao, Piotr Berman, Mary V. Ashley, Bhaskar Das Gupta, Wanpracha Art Chaovalitwongse, Tanya Y. Berger-Wolf

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

zbMATH Keywords

triangle packingapproximation hardnesscovering and packing problemssibling reconstruction in wild population

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Combinatorial optimization (90C27)

Related Items (2)

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

This page was built for publication: On approximating four covering and packing problems