Ami Paz
A (2+epsilon)-Approximation for Maximum Weight Matching in the
Semi-Streaming Model
I will present our new (2+epsilon)-approximation
algorithm for the maximum weight matching problem in the
semi-streaming model, that was presented in SODA 2017.
We will start by discussing the local-ratio technique, a simple,
sequential approximation paradigm we use in the algorithm. Then, we
will consider the variations needed in order to adjust this
technique to the semi-streaming model.
Based on a joint work with Gregory Schwartzman.