Piotr Sankowski

On 28.05.2015 as a part of our Foundation for Polish Science Algorithmic Miniworkshop series we will host Giuseppe F. Italiano from  University of Rome “Tor Vergata”. He will give a talk on his recent result on “Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching”. The abstract is given below.

We plan to have a group discussion and joint hamburger lunch after his talk.

Abstract:

We present the first deterministic data structures for maintaining
approximate  minimum vertex cover and maximum matching in a fully
dynamic graph in $o(\sqrt{m}\,)$ time per update. In particular, for
minimum vertex cover we provide deterministic data structures for
maintaining a $(2+\eps)$ approximation in $O(\log n/\eps^2)$ amortized
time per update. For maximum matching, we  show how to  maintain a
$(3+\eps)$ approximation in $O(m^{1/3}/\eps^2)$ {\em amortized} time
per update, and a $(4+\eps)$ approximation in $O(m^{1/3}/\eps^2)$ {\em
worst-case} time per update. Our data structure for fully dynamic
minimum vertex cover is essentially near-optimal and settles an open
problem by Onak and Rubinfeld~\cite{OnakR10}.

Joint work with Sayan Bhattacharya and Monika Henzinger.