BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260430T060120Z
UID:Seminar-ACS-1337@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Karteek Sreenivasaiah:MAILTO:Karteek.Sreenivasaiah@liverpool.ac.uk
DTSTART:20260429T130000
DTEND:20260429T140000
SUMMARY:Algorithms and Computing Systems Series
DESCRIPTION:Joachim Spoerhase: A Rounding Strategy for Approximating Network Design Problems\n\nA classic approach to design approximation algorithms for NP-hard network design problems such as the travelling salesman problem (TSP) or Steiner tree is to identify a (usually simple) combinatorial structure that approximates the hard problem. I will discuss an algorithmic strategy to improve upon the resulting (sometimes long-standing) bounds. The idea is to reduce the cost of the combinatorial structure by combining it with a randomly sampled structure extracted from a linear-programming relaxation. I will give a (high-level) overview on how this approach has been applied to Steiner tree and TSP to give the currently best approximation algorithms. I will also discuss a related recent work of mine (jointly with Martin Böhm, Zachary Friggstad, and Tobias Mömke) on variants of TSP.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1337
LOCATION:GH223
END:VEVENT
END:VCALENDAR