Tight approximability results for test set problems in bioinformatics
DOI10.1016/J.JCSS.2005.02.001zbMATH Open1076.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
Recommendations
Approximation algorithmsLower BoundsMinimum cost probe set problemsString BarcodingTest set problems
Protein sequences, DNA sequences (92D20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cites Work
- A threshold of ln n for approximating set cover
- A Mathematical Theory of Communication
- Title not available (Why is that?)
- Algorithms on Strings, Trees and Sequences
- Approximation algorithms for combinatorial problems
- Approximation algorithms for the test cover problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Zero knowledge and the chromatic number
- Title not available (Why is that?)
Cited In (21)
- Title not available (Why is that?)
- Combinatorial Pattern Matching
- Approximating the online set multicover problems via randomized winnowing
- Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
- Approximation complexity of metric dimension problem
- Algorithm Theory - SWAT 2004
- Approximation algorithms for a genetic diagnostics problem
- Faster Algorithm for the Set Variant of the String Barcoding Problem
- On optimal approximability results for computing the strong metric dimension
- Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
- Approximation for the minimum cost doubly resolving set problem
- Low-dimensional representation of genomic sequences
- On approximation complexity of metric dimension problem
- An improved configuration checking-based algorithm for the unicost set covering problem
- On the complexity and approximation of non-unique probe selection using \(d\)-disjunct matrix
- Phage typing sets
- On approximation algorithm for the edge metric dimension problem
- Non-unique probe selection and group testing
- A novel approach for detecting multiple rumor sources in networks with partial observations
- Parameterized lower bound and inapproximability of polylogarithmic string barcoding
- 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)
