BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260908T223847Z
UID:Seminar-dept-1248@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20241015T130000
DTEND:20241015T140000
SUMMARY:School Seminar Series
DESCRIPTION:Parinya Chalermsook: Fast and Survivable Network Design\n\nDesigning the cost-effective network (subgraph) that is guaranteed to be resilient against node or link failures is a fundamental problem in algorithms and optimization. The seminal result of Jain (2001) presents an elegant polynomial-time 2-approximation algorithm for a very general class of survivable network design problems. In this talk, we consider the question of achieving the same guarantee with a fast (near-linear time) algorithm. We show a fast algorithm for the case of k-Edge Connected Spanning Subgraphs (kECSS), a large and natural subclass of survivable network design that has received a lot of attention for more than 3 decades. \n\n\n\nJoint with C. Huang, D. Nanongkai, T. Saranurak, P. Sukprasert, and S. Yingcharoenthawornchai \n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1248
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR