跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.21294 · v2

Constant-Factor Matching-Size Estimation in Random-Order Streams

首次提交 2026-11-16 23:56
版本更新 2026-11-18 05:07
雷达观测 2026-11-19 19:08
arXiv ↗PDF ↗

摘要

We give a one-pass algorithm that estimates the maximum matching size of an arbitrary simple graph within a constant factor using O(log⁡2n)O(\log^2 n) bits of space. The edges arrive exactly once in uniformly random order. The algorithm succeeds with probability at least 2/32/3, does not require the number of edges in advance, and has worst-case total running time O((m+1)log⁡(n+2))O((m+1)\log(n+2)) on a word RAM. Kapralov, Khanna, and Sudan (SODA 2014) obtained a polylogarithmic approximation in polylogarithmic space. Kapralov, Mitrović, Norouzi-Fard, and Tardos (SODA 2020) subsequently gave a constant-factor approximation from independent uniform edge samples and an O(log⁡2n)O(\log^2 n)-approximation in random order. We obtain a constant factor in the latter model with the same O(log⁡2n)O(\log^2 n) space bound. The main ingredient is a comparison between the memory states of a recursive sampling algorithm under sampling with and without replacement. We account jointly for the sampled edges retained by the recursion and the positions at which they arrived. Randomized thresholds limit the additional information stored in numerical counters. A bound on the expected work of the entire recursion then removes the loss from its logarithmic depth. The resulting estimator repeatedly improves a coarse estimate while storing only one recursion stack.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

仅对比实际观测的元数据,不代表 PDF 正文或实验变化。版本可能不连续;带删除线为移除,下划线为新增。

这两个版本的已观测标题、作者、分类、摘要和备注没有变化。正文是否变化请核对原文。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v2 · 2026-11-18 05:07 · 最新观测版本

Constant-Factor Matching-Size Estimation in Random-Order Streams

We give a one-pass algorithm that estimates the maximum matching size of an arbitrary simple graph within a constant factor using O(log⁡2n)O(\log^2 n) bits of space. The edges arrive exactly once in uniformly random order. The algorithm succeeds with probability at least 2/32/3, does not require the number of edges in advance, and has worst-case total running time O((m+1)log⁡(n+2))O((m+1)\log(n+2)) on a word RAM. Kapralov, Khanna, and Sudan (SODA 2014) obtained a polylogarithmic approximation in polylogarithmic space. Kapralov, Mitrović, Norouzi-Fard, and Tardos (SODA 2020) subsequently gave a constant-factor approximation from independent uniform edge samples and an O(log⁡2n)O(\log^2 n)-approximation in random order. We obtain a constant factor in the latter model with the same O(log⁡2n)O(\log^2 n) space bound. The main ingredient is a comparison between the memory states of a recursive sampling algorithm under sampling with and without replacement. We account jointly for the sampled edges retained by the recursion and the positions at which they arrived. Randomized thresholds limit the additional information stored in numerical counters. A bound on the expected work of the entire recursion then removes the loss from its logarithmic depth. The resulting estimator repeatedly improves a coarse estimate while storing only one recursion stack.

查看此版本解读 →查看此版本原文 ↗
v1 · 2026-11-16 23:56

Constant-Factor Matching-Size Estimation in Random-Order Streams

We give a one-pass algorithm that estimates the maximum matching size of an arbitrary simple graph within a constant factor using O(log⁡2n)O(\log^2 n) bits of space. The edges arrive exactly once in uniformly random order. The algorithm succeeds with probability at least 2/32/3, does not require the number of edges in advance, and has worst-case total running time O((m+1)log⁡(n+2))O((m+1)\log(n+2)) on a word RAM. Kapralov, Khanna, and Sudan (SODA 2014) obtained a polylogarithmic approximation in polylogarithmic space. Kapralov, Mitrović, Norouzi-Fard, and Tardos (SODA 2020) subsequently gave a constant-factor approximation from independent uniform edge samples and an O(log⁡2n)O(\log^2 n)-approximation in random order. We obtain a constant factor in the latter model with the same O(log⁡2n)O(\log^2 n) space bound. The main ingredient is a comparison between the memory states of a recursive sampling algorithm under sampling with and without replacement. We account jointly for the sampled edges retained by the recursion and the positions at which they arrived. Randomized thresholds limit the additional information stored in numerical counters. A bound on the expected work of the entire recursion then removes the loss from its logarithmic depth. The resulting estimator repeatedly improves a coarse estimate while storing only one recursion stack.

查看此版本解读 →查看此版本原文 ↗