BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Events at IITGN - ECPv4.6.11.1//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Events at IITGN
X-ORIGINAL-URL:http://events.iitgn.ac.in
X-WR-CALDESC:Events for Events at IITGN
BEGIN:VEVENT
DTSTART;TZID=Asia/Kolkata:20190107T120000
DTEND;TZID=Asia/Kolkata:20190107T130000
DTSTAMP:20190121T175450
CREATED:20190108T080251Z
LAST-MODIFIED:20190121T093117Z
UID:25686-1546862400-1546866000@events.iitgn.ac.in
SUMMARY:The Parameterized Complexity of Network Design Problems
DESCRIPTION:Network Design Problems\, which concern designing minimum cost networks that satisfy a given set of connectivity constraints\, 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”. \nIn this talk\, we will discuss some recent results on the parameterized complexity of network design problems. This includes problems such as Steiner Tree\, Connectivity Augmentation\, Minimum Equivalent Graph\, and several others. This talk is based on results that appeared in SODA 18\, WADS 17\, ICALP 14 and some recent unpublished work.Discipline/Coordinating Entity: Computer Science and Engineering \n
URL:http://events.iitgn.ac.in/event/the-parameterized-complexity-of-network-design-problems/
CATEGORIES:Events
END:VEVENT
END:VCALENDAR