标题: | Learning a hidden graph |
作者: | Chang, Huilan Fu, Hung-Lin Shih, Chih-Huai 应用数学系 Department of Applied Mathematics |
关键字: | Combinatorial search;Graph learning;Competitive group testing;Complex model |
公开日期: | 1-十二月-2014 |
摘要: | 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. |
URI: | http://dx.doi.org/10.1007/s11590-014-0751-9 http://hdl.handle.net/11536/123884 |
ISSN: | 1862-4472 |
DOI: | 10.1007/s11590-014-0751-9 |
期刊: | OPTIMIZATION LETTERS |
起始页: | 2341 |
结束页: | 2348 |
显示于类别: | Articles |
文件中的档案:
If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.