Tata Institute of Fundamental Research
Dynamic Primal Dual Algorithms for Vertex Cover and Matching
STCS Seminar
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)
Abstract:
Abstract: Consider a scenario where we are given an input graph $G = (V, E)$, and at each time-step either a new edge is inserted into the graph or an already existing edge is deleted from the graph. In this dynamic setting, we want to maintain an approximately minimum vertex cover and an approximately maximum matching in $G$.
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).
| 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)
Abstract:
Abstract: Consider a scenario where we are given an input graph $G = (V, E)$, and at each time-step either a new edge is inserted into the graph or an already existing edge is deleted from the graph. In this dynamic setting, we want to maintain an approximately minimum vertex cover and an approximately maximum matching in $G$.
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).
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).