Tata Institute of Fundamental Research
Parameterized Complexity of Network Design Problems
STCS Seminar
Speaker:
Pranabendu Mirsa (Department of Informatics
University of Bergen
Norway)
Organiser:
Jaikumar Radhakrishnan
Date:
Thursday, 10 Jan 2019, 14:30 to 15:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Pranabendu Mirsa (Department of Informatics University of Bergen Norway) |
| Organiser: | Jaikumar Radhakrishnan |
| Date: | Thursday, 10 Jan 2019, 14:30 to 15:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.