Computing Optimal Epsilon-Nets Is as Easy as Finding an Unhit Set
Computing Optimal Epsilon-Nets Is as Easy as Finding an Unhit Set
复制标题
计算最佳 Epsilon-Nets 就像找到未命中的集合一样简单
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Nabil H. Mustafa
中科院分区：
文献类型：
--
作者：
Nabil H. Mustafa
鉴于带有VC -Dimension D的设置系统（X，R），Haussler和Welzl（1987）的著名结果表明，有一个大小O（d log 1）的-Net算法是简单的：但是，对于许多几何系统，将统一的随机样品从X上进行，从那以后，在此论文中，有很多工作提出了改进的边界和算法，我们考虑以下天然算法来计算-NET：以初始随机样本n开始。 ，并将O（1）从s随机选择的点，我们证明上述算法在所有已知的几何套装系统中计算的 - 不对称最佳大小的网络。特别是对Oracle。
Given a set system (X,R) with VC-dimension d, the celebrated result of Haussler and Welzl (1987) showed that there exists an -net for (X,R) of size O ( d log 1 ) . Furthermore, the algorithm is simple: just take a uniform random sample from X! However, for many geometric set systems this bound is sub-optimal and since then, there has been much work presenting improved bounds and algorithms tailored to specific geometric set systems. In this paper, we consider the following natural algorithm to compute an -net: start with an initial random sample N . Iteratively, as long as N is not an -net for R, pick any unhit set S ∈ R (say, given by an Oracle), and add O(1) randomly chosen points from S to N . We prove that the above algorithm computes, in expectation, -nets of asymptotically optimal size for all known cases of geometric set systems. Furthermore, it makes O ( 1 ) calls to the Oracle. In particular, this implies that computing optimal-sized -nets are as easy as computing an unhit set in the given set system. 2012 ACM Subject Classification Theory of computation → Sketching and sampling