Seminars

View all Seminars  |  Download ICal for this event

Parameterized Complexity of Network Design Problems

Series: Department Seminar

Speaker: Pranabendu Misra, MPI, Saarbrucken

Date/Time: Jan 17 11:00:00

Location: CSA Seminar Hall (Room No. 254, First Floor)

Faculty Advisor:

Abstract:
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.

Speaker Bio:
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