Learning a hidden matching
Learning a hidden matching
复制标题
DOI：
10.1109/sfcs.2002.1181943
复制
发表时间：
2002-11
期刊：
影响因子：
--
通讯作者：
N. Alon;R. Beigel;S. Kasif;S. Rudich;B. Sudakov
中科院分区：
文献类型：
--
作者：
N. Alon;R. Beigel;S. Kasif;S. Rudich;B. Sudakov
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 ( 1/2 +o(1))(n/2) upper bound and a nearly matching 0.32(n/2) 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 O(n log n) upper bound, which is best possible (even for randomized fully adaptive algorithms).
