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