Campus Event Calendar
Event Entry
What and Who
(1+\eps)-Approximate Dynamic Matching in Truly Sublinear Time
Peter Kiss
University of Warwick
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 14 February 2023
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
We present the first algorithm which can estimate the maximum matching size with arbitrary small additive slack in time polynomially sub-linear with respect to the number of edges present in the graph for any input graph. Previous algorithms either required an approximation ratio of 1.499 or for the input graph to have small maximum degree. From this result we simply derive the first algorithm which can maintain a (1+\eps) approximation of the maximum matching size under edge insertions and deletions in update time sub-linear in n.
Contact
Roohani Sharma
+49 681 9325 1116
--email hidden
Virtual Meeting Details
Zoom
527 278 8807
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
If you wish to attend the talk online, but do not have the zoom password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.
Roohani Sharma, 02/12/2023 22:35
Roohani Sharma, 02/08/2023 18:23 -- Created document.
Roohani Sharma, 02/08/2023 18:23 -- Created document.