Tight approximability results for test set problems in bioinformatics

DOI10.1016/J.JCSS.2005.02.001zbMATH1076.68113OpenAlexW2074293104MaRDI QIDQ2485280FDOQ2485280

Authors Piotr Berman, Ming-Yang Kao, Bhaskar Dasgupta

Publication date 3 August 2005

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.2005.02.001

zbMATH Keywords

Approximation algorithmsLower BoundsMinimum cost probe set problemsString BarcodingTest set problems

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Algorithm Theory - SWAT 2004
• scientific article; zbMATH DE number 1875415
• Faster Algorithm for the Set Variant of the String Barcoding Problem
• Approximation algorithms for the test cover problem
• scientific article; zbMATH DE number 1947395

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256762 (Why is no real title available?)
• scientific article; zbMATH DE number 1263202 (Why is no real title available?)
• scientific article; zbMATH DE number 1875415 (Why is no real title available?)
• A Mathematical Theory of Communication
• A threshold of ln n for approximating set cover
• Algorithms on Strings, Trees and Sequences
• Approximation algorithms for combinatorial problems
• Approximation algorithms for the test cover problem
• Zero knowledge and the chromatic number

Cited in

(21)

• Non-unique probe selection and group testing
• On approximation algorithm for the edge metric dimension problem
• On the complexity and approximation of non-unique probe selection using \(d\)-disjunct matrix
• Low-dimensional representation of genomic sequences
• Approximation algorithms for a genetic diagnostics problem
• On optimal approximability results for computing the strong metric dimension
• Phage typing sets
• Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
• scientific article; zbMATH DE number 1875415 (Why is no real title available?)
• Parameterized lower bound and inapproximability of polylogarithmic string barcoding
• On approximation complexity of metric dimension problem
• Approximation for the minimum cost doubly resolving set problem
• Approximation complexity of metric dimension problem
• Algorithm Theory - SWAT 2004
• Approximating the online set multicover problems via randomized winnowing
• An improved configuration checking-based algorithm for the unicost set covering problem
• Faster Algorithm for the Set Variant of the String Barcoding Problem
• A novel approach for detecting multiple rumor sources in networks with partial observations
• Combinatorial Pattern Matching
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
• On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results

This page was built for publication: Tight approximability results for test set problems in bioinformatics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2485280)