Learning a hidden graph
檔案
- 000345317500015.pdf (140.6 KB, Adobe PDF)
日期
2014-12-01
類型
系所
期刊名稱
OPTIMIZATION LETTERS
卷期與頁次
頁 2341–2348
ISSN
1862-4472
語言
英文
摘要
We study the problem of learning a hidden graph by edge-detecting queries, each of which tells whether a set of vertices induces an edge of the hidden graph or not. We provide a new information-theoretic lower bound and give a more efficient adaptive algorithm to learn a general graph with n vertices and m edges in m log n + 10m + 3n edge-detecting queries.