Speaker: |
Sayan Bhattacharya (Institute of Mathematical Sciences IV Cross Road, CIT Campus Taramani Chennai 600113) |

Organiser: |
Jaikumar Radhakrishnan |

Date: |
Wednesday, 12 Aug 2015, 14:30 to 15:30 |

Venue: |
A-212 (STCS Seminar Room) |

(Scan to add to calendar)

Our main result is a deterministic primal-dual algorithm for this problem. The algorithm maintains a $(2+\epsilon)$-approximate minimum vertex cover in $O(\log n/\epsilon^2)$ amortized update time, where n denotes the number of nodes. This answers an open question from Onak and Rubinfield [STOC' 2010]. We can also maintain a $(3+\epsilon)$-approximate maximum matching in $O(m^{1/3})$ amortized update time, where m denotes the number of edges in the graph.

We also describe extensions of our framework to dynamic set cover and dynamic b-matching problems (joint work with Monika Henzinger and Guiseppe Italiano, ased on work that appeared in SODA 2015 and ICALP 2015).