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

Date, Time and Location

Tuesday, 14 February 2023
30 Minutes
E1 4


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.


Roohani Sharma
+49 681 9325 1116
--email hidden

Virtual Meeting Details

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

Roohani Sharma, 02/12/2023 22:35
Roohani Sharma, 02/08/2023 18:23 -- Created document.