BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260915T194319Z
UID:Seminar-dept-379@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20150505T130000
DTEND:20150505T140000
SUMMARY:School Seminar Series
DESCRIPTION:Dr Marcin Pilipczuk: Sparsification for network design problems in planar graphs\n\nA well-established technique for designing polynomial-time approximation schemes (PTASes) for connectivity or network design problems on planar graphs is to first establish a spanner - a subgraph or minor of the input graph that contains a near-optimal solution, while at the same time has total cost bounded by f(epsilon) times the optimum cost (where epsilon is the accuracy parameter) - and then use a variant of the Baker's shifting technique to solve the problem on the spanner only. This approach turned out to be very fruitful, yielding PTASes on planar graph for such problems as Subset TSP, Steiner Tree, Steiner Forest. Moreover, recently, due to connections between cut problems in the primal graph and network design problems in the dual graph, we have seen a PTAS for Multiway Cut and a bicriteria PTAS for Bisection.\n\n\n\nIn our recent work with Michal Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen (available here: http://arxiv.org/abs/1306.6593), we used the insight from the aforementioned approximation schemes to design improved exact algorithms for (unweighted) Steiner Tree in planar graphs in the framework of fixed-parameter tractability: a subexponential algorithm and an efficient preprocessing routine (called a polynomial kernel) for the parameterization by the number of edges in the solution tree. Some results generalize to bounded-genus graphs, and also to the Steiner Forest and Multiway Cut problems.\n\n\n\nIn the talk I will give an overview of both the spanner framework for designing PTASes on planar graphs and of recent results in parameterized complexity world, focusing on the Steiner Tree problem.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=379
LOCATION:Ashton Lecture Theater
END:VEVENT
END:VCALENDAR