BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20200117T120000Z
UID:fcd0d3e94c4554ea84dcd0c79e2604ee-43
DTSTAMP:19700101T120011Z
DESCRIPTION:Parameterized Complexity of Network Design Problems
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/43/parameterized-complexity-of-network-design-problems/
SUMMARY: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.
DTSTART:20200117T120000Z
END:VEVENT
END:VCALENDAR