Learning a Hidden Matching Combinatorial Identification of Hidden Matchings with Applications to Whole Genome Sequencing
2002
We consider the problem of learning a matching (i.e., a graph in which all vertices have degree 0 or 1) in a model where the only allowed operation is to query whether a set of vertices induces an edge. This is motivated by a problem that arises in molecular biology. In the deterministic nonadaptive setting, we prove a upper bound and a nearly matching lower bound for the minimum possible number of queries. In contrast, if we allow randomness then we obtain (by a randomized, nonadaptive algorithm) a much lower upper bound, which is best possible
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
9
References
1
Citations
NaN
KQI