Nearly optimal edge estimation with independent set queries
Nearly optimal edge estimation with independent set queries
复制标题
使用独立集查询进行近乎最优的边缘估计
DOI：
10.1137/1.9781611975994.177
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Waingarten, Erik
中科院分区：
文献类型：
--
作者：
Chen, Xi;Levi, Amit;Waingarten, Erik
研究了一个未知无向图G =（[n]，E）的边数估计问题.当询问顶点的子集S [n]时，独立集预言机回答是否是G中的独立集。我们的第一个主要结果是一个算法，该算法使用· poly（logn，1/n）独立集查询计算图的边数m的（1 + n）-近似。这改进了Beame等人[3]的· poly（logn，1/ε）的上界。我们的第二个主要结果表明，/polylog（n）独立集查询是必要的，从而建立我们的算法是最佳的一个因素的poly（logn，1/n）。
We study the problem of estimating the number of edges of an unknown, undirected graphG= ([n],E) with access to an independent set oracle. When queried about a subsetS⊆ [n] of vertices, the independent set oracle answers whetherSis an independent set inGor not. Our first main result is an algorithm that computes a (1 +ϵ)-approximation of the number of edgesmof the graph using · poly(logn, 1/ϵ) independent set queries. This improves the upper bound of · poly(logn, 1/ε) by Beame et al. [3]. Our second main result shows that /polylog(n) independent set queries are necessary, thus establishing that our algorithm is optimal up to a factor of poly(logn, 1/ϵ).
登录
查看更多内容
DOI：
10.1109/focs.2015.44
发表时间：
2015-04
期刊：
2015 IEEE 56th Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
T. Eden;Amit Levi;D. Ron;C. Seshadhri
通讯作者：
T. Eden;Amit Levi;D. Ron;C. Seshadhri
使用独立集预言机进行边缘估计
DOI：
10.1145/3404867
发表时间：
2017
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
P. Beame;Sariel Har;Sivaramakrishnan Natarajan Ramamoorthy;Cyrus Rashtchian;Makrand Sinha
通讯作者：
Makrand Sinha
近似有界度和一般稀疏图中属性的距离
DOI：
10.1145/1497290.1497298
发表时间：
2009
期刊：
ACM Trans. Algorithms
影响因子：
--
作者：
S. Marko;D. Ron
通讯作者：
D. Ron
一种通过边缘采样计算任意子图的简单次线性时间算法
DOI：
--
发表时间：
2018
期刊：
Information Technology Convergence and Services
影响因子：
--
作者：
Sepehr Assadi;M. Kapralov;S. Khanna
通讯作者：
S. Khanna
DNA 文库筛选产生的组合问题。
DOI：
--
发表时间：
2004
期刊：
Le Mathematiche Vol.LIX
影响因子：
--
作者：
M.Jimbo;M.Mueller
通讯作者：
M.Mueller