对最大匹配尺寸的均匀边缘样本进行空间有效估计

作者：Michael Kapralov,Slobodan Mitrović,Ashkan Norouzi-Fard,Jakab Tardos

摘要：给定具有n个顶点和m个边的输入图G的边的iid样本的源，需要多少个样本来计算G中的最大匹配大小的常数因子近似？而且，是否有可能在少量空间中获得这样的估计？我们表明，一方面，使用非平凡的次线性（m）个样本不能解决这个问题：需要m1-o（1）个样本。另一方面，存在用于处理样本的令人惊讶的空间有效算法：O（log2n）位空间足以计算估计。

我们的主要技术工具是用于匹配的新的剥离类型算法，我们使用递归采样过程进行模拟，该过程关键地确保以适当更高的采样率提供来自图的“密集”区域的局部邻域信息。我们表明，探测深度和采样率之间的微妙平衡使我们的模拟不会在对数级递归水平上失去精度，并实现恒定因子近似。从随机样本中匹配大小估计的先前最佳结果是logO（1）n近似。

我们的算法还产生一个常数因子近似局部计算算法（LCA），用于从任何顶点开始匹配O（dlogn）探测。以前的方法是基于随机贪婪的局部模拟，这需要花费O（d）时间{\ em em对起始顶点或边缘的期望}（Yoshida et al'09，Onak et al'12），并且无法实现更好的比d2运行时。有趣的是，我们还表明，与我们的算法不同，随机贪婪的局部模拟是最有效的先验结果的基础，确实需要$ \ wt {\ Omega}（d ^ 2）\ gg O（d \ log n）$即使对于d = exp（Θ（logn ----√）），最坏情况边缘的时间。

原文标题：Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

原文摘要：

地址：https://arxiv.org/abs/1907.05725