単一パス・セミストリーミング最大マッチング：Greedy が最適であることを証明

Greedy is optimal for single-pass semi-streaming matching

グラフストリーミングにおける最大マッチング問題について、単一パスのセミストリーミングアルゴリズム（決定的・乱択を問わず）が近似比 1/2 を超えられないことを証明。これはモデル導入以来20年以上未解決だった問題で、単純な Greedy アルゴリズムの最適性を示す。証明は著者らが以前導入した「ブループリント」フレームワークを用い、最適なブループリントを構成することで下界を導出。さらに、プリエンプションを伴うオンラインマッチングの競争比も 1/2 が最適であることを示し、こちらも Greedy が最適であることを明らかにした。