Theory Seminar

: A (2+eps )-Approximation for Maximum Weight Matching in the Semi-Streaming Model

Seth Pettie

Associate Professor
University of Michigan
Friday, February 03, 2017
10:30am - 11:30am
BBB 3725

Add to Google Calendar

About the Event

Authors Ami Paz and Gregory Schwartzman present a simple deterministic single-pass (2+eps )-approximation algorithm for the maximum weight matching problem in the semi-streaming model. This improves upon the currently best known approximation ratio of (3.5+eps ). Theirs algorithm uses O(n log^2 n) space for constant values of eps . It relies on a variation of the local-ratio theorem, which may be of independent interest in the semi-streaming model.

Additional Information

Sponsor(s): CSE

Open to: Public