← 研踪 PaperTrailarXiv:2611.21294 · v1
Constant-Factor Matching-Size Estimation in Random-Order Streams
首次提交 2026-11-16 23:56
版本更新 2026-11-16 23:56
雷达观测 2026-11-17 16:10
摘要
We give a one-pass algorithm that estimates the maximum matching size of an arbitrary simple graph within a constant factor using bits of space. The edges arrive exactly once in uniformly random order. The algorithm succeeds with probability at least , does not require the number of edges in advance, and has worst-case total running time 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 -approximation in random order. We obtain a constant factor in the latter model with the same 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.
观测到的版本
相邻记录可能跳过中间版本;首次发现 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 bits of space. The edges arrive exactly once in uniformly random order. The algorithm succeeds with probability at least , does not require the number of edges in advance, and has worst-case total running time 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 -approximation in random order. We obtain a constant factor in the latter model with the same 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 bits of space. The edges arrive exactly once in uniformly random order. The algorithm succeeds with probability at least , does not require the number of edges in advance, and has worst-case total running time 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 -approximation in random order. We obtain a constant factor in the latter model with the same 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.
查看此版本解读 →查看此版本原文 ↗