贪心算法竟是最优解？

Greedy is optimal for single-pass semi-streaming matching

在图流算法领域，一个困扰学界二十多年的难题终于被攻克。Sepehr Assadi、Max Jiang和Mars Xiang的最新研究证明，在单次扫描的Semi-Streaming模型下，没有任何确定性或随机化算法能超越贪心算法的表现。这项成果不仅确立了朴素贪心算法的最优性，还解决了在线匹配中带有抢占机制的竞争比问题。研究团队利用独特的blueprint framework，通过构建组合对象成功推导出了这一理论下界，彻底终结了关于该模型性能上限的争论。

"我们证明了，在单次扫描的semi-streaming算法中，没有任何确定性或随机化方法能获得优于二分之一的最大匹配近似比。"