On the Approximability of Some Haplotyping Problems

DOI10.1007/978-3-642-02158-9_3zbMath1243.90183OpenAlexW1960027219MaRDI QIDQ3638438

No author found.

Publication date: 2 July 2009

Published in: Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02158-9_3

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Genetics and epigenetics (92D10) Computational methods for problems pertaining to biology (92-08)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Polynomial and APX-hard cases of the individual haplotyping problem
• The complexity of the single individual SNP haplotyping problem
• A polynomial case of the parsimony haplotyping problem
• Haplotyping Populations by Pure Parsimony: Complexity of Exact and Approximation Algorithms
• A Greedy Heuristic for the Set-Covering Problem
• On the hardness of approximating minimization problems
• Multiway cuts in node weighted graphs