Parameterized Complexity of Network Design Problems by Pranabendu Misra

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

Department of Computer Science and Automation
Department Seminar

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)

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.

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