School of Technology and Computer Science Seminars
Parameterized Complexity of Network Design Problems
by Pranabendu Mirsa (University of Bergen, Norway)
Thursday, January 10, 2019
from
to
(Asia/Kolkata)
at A-201 (STCS Seminar Room)
at A-201 (STCS Seminar Room)
Description |
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 different framework for dealing with computational intractability, where typically we try to design fast algorithms to solve the problem on those instances which admit a ``small cost solution''. In this talk we will look at some recent results on the parameterized complexity of network design problems, and future directions for research. |
Organised by | Jaikumar Radhakrishnan |