查看PDF HTML（实验性）摘要：我们证明没有任何单遍流式算法（确定性或随机性）能够实现大于半数的最大匹配问题的近似。这意味着朴素的贪婪算法是最优的，回答了自二十多年前该模型引入以来在图流式文献中悬而未决的开放问题。我们的证明遵循作者之前提出的“蓝图框架”，该框架将证明流式匹配的下界归结为构造某些组合对象，即蓝图。我们展示了蓝图的最优构造，当在该框架中使用时，可推导出我们的流式匹配下界。我们的结果还表明，带有抢占的在线匹配的最优竞争比为二分之一，再次匹配朴素的贪婪算法，解决了这个开放问题。注释：23页，3幅图。版本2：修正了整个文档中的类型错误和小语言问题。主题：数据结构与算法 (cs.DS)；计算复杂性 (cs.CC) 引用为：arXiv:2607.14656 [cs.DS]（或arXiv:2607.14656v2 [cs.DS]，适用于本版本） https://doi.org/10.48550/arXiv.2607.14656 arXiv发布的DOI通过DataCite 提交历史 来源：Sepehr Assadi [查看邮件] [v1] 2026年7月16日 星期四 07:22:45 UTC (39 KB) [v2] 2026年7月20日 星期一 02:47:00 UTC (39 KB)