Skip to main content

Sayan Bhattacharya: Dynamic primal-dual algorithms for vertex cover and matching

Time: Mon 2016-05-02 12.00

Location: Room 4523, Lindstedtsvägen 5, KTH CSC

Participating: Sayan Bhattacharya, Institute of Mathematical Sciences Chennai

Export to calendar

PRACTICALITIES

Lunch is served at 12:00 noon (register at this doodle at the latest the Saturday before, but preferably earlier). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for 1½-2 hours of more technical discussions.

 

ABSTRACT

Consider a scenario where we are given an input graph G = (V, E) with n nodes and m edges. The node-set of the graph remains unchanged over time, but the edge-set is dynamic. Specifically, at each time-step an adversary either inserts an edge into the graph, or deletes an already existing edge from the graph. The problem is to maintain an approximately maximum matching (resp. minimum vertex cover) in this dynamic setting.

We present a clean primal-dual algorithm for this problem that has O(log n/\epsilon^2) amortized update time. The approximation ratio of the algorithm is (2+\epsilon) for minimum vertex cover and (3+\epsilon) for maximum matching. We also show how to extend this result to the dynamic b-matching and set-cover problems. This is the first application of the primal-dual framework in a dynamic setting.

Joint work with M. Henzinger and G. F. Italiano (based on papers that appeared in SODA 2015 and ICALP 2015).

BIOGRAPHIC SKETCH

Sayan Bhattacharya is a faculty member at the Institute of Mathematical Sciences (Chennai, India). He received his Phd from Duke University (Durham, USA) in December, 2012. Subsequently, he was a postdoctoral researcher at the Max Planck Institute for Informatics (Saarbrucken, Germany) and at the University of Vienna (Vienna, Austria). His current research interests are in Dynamic Graph Algorithms, Data Structures and Online Algorithms.