BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260415T183526Z
UID:Seminar-ACS-1328@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Karteek Sreenivasaiah:MAILTO:Karteek.Sreenivasaiah@liverpool.ac.uk
DTSTART:20260415T130000
DTEND:20260415T140000
SUMMARY:Algorithms and Computing Systems Series
DESCRIPTION:Anish Mukherjee: Blossoms in the Stream: Simpler and Faster Matchings\n\nHow many passes are really needed to compute a near-maximum matching in a massive graph using only semi-streaming space? I will present a deterministic (1+ε)-approximation algorithm for maximum matching in general graphs that significantly improves the dependence on ε in the number of passes. The algorithm is based on maintaining structured collections of alternating trees and handling blossoms to efficiently capture short augmenting paths. This leads to both an improved bound and a conceptually cleaner framework. The same ideas also yield corresponding improvements in MPC and CONGEST. This is joint work with Slobodan Mitrović, Piotr Sankowski, and Wen-Horng Sheu.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1328
LOCATION:GH223
END:VEVENT
END:VCALENDAR