BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/821
DTSTAMP:20230914T125939Z
SUMMARY:Maximum Matching in the Semi-Streaming Model in Constant Number of 
 Passes
DESCRIPTION:Speaker: Sumedh Vinod Tirodkar\n\nAbstract: \nWe consider the m
 aximum matching problem in the semi-streaming model formalized by Feigenba
 um et al. that is inspired by giant graphs of today.  The input is a stre
 am of edges\, and an algorithm can use a memory of O(n\\poly\\log n) to ou
 tput a maximum matching. If an algorithm goes over the stream k times\, th
 en it is called a k pass algorithm. Maximal matching algorithm is a 2-appr
 oximation one-pass algorithm\, and a big open problem is to find an algori
 thm which does better in one-pass.\n\nWe begin by giving a two-pass (1/2 +
  1/16)-approximation algorithm for triangle-free graphs and a two-pass (1/
 2 + 1/32)-approximation algorithm for general graphs\; these improve the a
 pproximation ratios of 1/2 + 1/52 for bipartite graphs and 1/2 + 1/140 for
  general graphs by Konrad\, Magniez\, and Mathieu.  In three passes\, we 
 achieve approximation ratios of 1/2 + 1/10 for triangle-free graphs and 1/
 2 + 1/19.753 for general graphs.  We also give a multi-pass algorithm whe
 re we bound the number of passes precisely---we give a (2/3 -\\epsilon)-ap
 proximation algorithm that uses 2/(3\\epsilon) passes for triangle-free gr
 aphs and 4/(3\\epsilon) passes for general graphs.  Our algorithms are si
 mple and combinatorial\, use O(n \\log(n)) space\, and have O(1) update ti
 me per edge.\n\nWe extend the multipass algorithm to give a (3/4-\\epsilon
 )-approximation algorithm that uses O(\\log(1/\\epsilon)/\\epsilon) passes
 . This algorithm gives ideas for an (1-\\epsilon)-approximation determinis
 tic algorithm. Note that there is no known deterministic algorithm for gen
 eral graphs which achieves (1-\\epsilon)-approximation in constant number 
 of passes.\n
URL:https://www.tcs.tifr.res.in/web/events/821
DTSTART;TZID=Asia/Kolkata:20171027T171500
DTEND;TZID=Asia/Kolkata:20171027T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR