Department of Computer Science and Automation
Speaker : Pranabendu Misra, MPI, Saarbrucken
Title : Parameterized Complexity of Network Design Problems
Date : Friday, January 17, 2020
Time : 11:00 AM
Venue : CSA Seminar Hall (Room No. 254, First Floor)
Network Design Problems, which concern designing minimum cost networks that satisfy given set of “connectivity constrains”, are very well studied in computer science and combinatorial optimization. Almost all these problems are NP-hard, and a number of results are known about them in the realm of approximation algorithms. Parameterized Complexity is a framework for dealing with computational intractability, where (typically) we try to optimally solve those problem instances which admit a “small cost solution” or some other nice structural properties. In this talk we will look at some recent results on the parameterized complexity of network design problems, and future directions for research.
Biography of the speaker
Pranabendu Misra is a postdoctoral fellow at the Max Planck Institute for Informatics, Saarbrucken, Germany. He obtained his PhD in Computer Science from the Institute of Mathematical Sciences, Chennai, India, advised by Saket Saurabh. His primary research interests lie in graph theory and algorithms focusing on Parameterized Complexity. He is also interested in approximation algorithms, matroids, fault tolerant graphs, matching under preferences, de-randomization.
Host Faculty : Prof. Matthew Jacob
ALL ARE WELCOME