Greedy ist optimal: Ein Durchgang genügt für semi-streaming Matching

Greedy is optimal for single-pass semi-streaming matching

Eine neue Arbeit von Sepehr Assadi, Max Jiang und Mars Xiang beweist, dass kein einpassiger Semi-Streaming-Algorithmus – weder deterministisch noch randomisiert – eine bessere als 1/2-Approximation für das Maximum-Matching-Problem erreichen kann. Damit wird die Optimalität des naiven Greedy-Algorithmus bestätigt und eine offene Frage aus der Graph-Streaming-Literatur beantwortet, die seit über zwei Jahrzehnten bestand. Der Beweis nutzt das von den Autoren zuvor eingeführte "Blueprint-Framework" und liefert eine optimale Konstruktion der benötigten kombinatorischen Objekte. Zudem ergibt sich, dass auch das optimale Competitive Ratio für Online-Matching mit Preemption bei 1/2 liegt, was eine weitere offene Frage klärt.