BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:America/New_York
BEGIN:DAYLIGHT
DTSTART:20240310T030000
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
RRULE:FREQ=YEARLY;BYDAY=2SU;BYMONTH=3
TZNAME:EDT
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20231105T010000
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
RRULE:FREQ=YEARLY;BYDAY=1SU;BYMONTH=11
TZNAME:EST
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20241107T105438Z
UID:b7820426-ea2c-4ba3-ad43-6ad8427730e6
DTSTART;TZID=America/New_York:20240228T160000
DTEND;TZID=America/New_York:20240228T170000
CREATED:20240228T002346
DESCRIPTION:Abstract: This talk concerns universal Steiner trees (USTs). In
formally\, a UST is a single spanning tree that is a good approximation fo
r every instance of Steiner tree. More formally\, an α-approximate univer
sal Steiner tree (UST) of a graph G for root vertex r is a spanning tree T
such that\, for any vertex subset S containing r\, the cost of the minima
l subtree of T connecting S is within an α factor of the cost of the mini
mum cost subgraph of G connecting S. α-approximate USTs immediately give
α-approximations for well-studied variants of Steiner tree such as online
or oblivious Steiner tree. Sub-linear-approximate USTs are known but neit
her the existence of nor poly-time algorithms for computing poly-logarithm
ic-approximate USTs were previously known. In this talk\, I will discuss t
he first construction of poly-logarithmic-approximate USTs which (nearly)
exponentially improve the approximation guarantees of previous constructio
ns and (nearly) match logarithmic lower bounds. The result is based on new
constructions of poly-logarithmic-quality graph hierarchies called strong
sparse partition hierarchies which may be interesting in their own right.
Roughly\, a strong sparse partition (i.e. each level of this hierarchy) i
s a vertex partition that provides deterministic guarantees on the number
of parts balls of appropriate radii intersect. Joint work with Costas Busc
h\, Da Qi Chen\, Arnold Filtser\, Daniel Hathcock and Rajmohan Rajaraman.
LAST-MODIFIED:20240228T002533
LOCATION:G575
SUMMARY:Polylogarithmic Universal Steiner Trees and Strong Sparse Partition
Hierarchies
URL:https://calendar.csail.mit.edu/events/279546
END:VEVENT
END:VCALENDAR