BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1325
DTSTAMP:20230914T125959Z
SUMMARY:A sublinear time algorithm for approximately perfect matchings in r
egular graphs
DESCRIPTION:Speaker: Varsha Dani (Golisano College of Computing and Informa
tion Sciences\, Rochester Institute of Technology\, U.S.A.)\n\nAbstract: \
nA breakthrough sequence of papers by Goel\, Kapralov\, and Khanna gave t
he first sublinear-time algorithms for finding large matchings in regular
bipartite graphs. The crown jewel of these is an $O(n \\log n)$ algorith
m to find a perfect matching\, based on the idea of randomly generated au
gmenting paths.\nWe discuss the extent to which the restrictions of being
regular and bipartite can be relaxed. In particular\, we will show that\
, for all d-regular (non-bipartite) graphs\, a matching using a (1-1/(d+1)
) fraction of the vertices can be found in O(n log d) time. At the heart o
f our algorithm is a new method for turning walks that alternate between m
atching and non-matching edges into alternating paths.\n
URL:https://www.tcs.tifr.res.in/web/events/1325
DTSTART;TZID=Asia/Kolkata:20230808T160000
DTEND;TZID=Asia/Kolkata:20230808T170000
LOCATION:A201
END:VEVENT
END:VCALENDAR