One Tree to Rule Them All: Polylogarithmic Universal Steiner Trees

A Google TechTalk, presented by D Ellis Hershkowitz, 2024-03-12 A Google Algorithms Seminar. ABSTRACT: One Tree to Rule Them All: Polylogarithmic Universal Steiner Trees and Strong Sparse Partition Hierarchies. This talk concerns universal Steiner trees (USTs). Informally, a UST is a single spanning tree that is a good approximation for every instance of Steiner tree. More formally, an α-approximate universal 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 minimal subtree of T connecting S is within an α factor of the cost of the minimum 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 neither the existence of nor poly-time algorithms for computing poly-logarithmic-approximate USTs were previously known. In this talk, I will discuss the first construction of poly-logarithmic-approximate USTs which (nearly) exponentially improve the approximation guarantees of previous constructions 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) is a vertex partition that provides deterministic guarantees on the number of parts balls of appropriate radii intersect. Joint work with Costas Busch, Da Qi Chen, Arnold Filtser, Daniel Hathcock and Rajmohan Rajaraman Bio: Ellis Hershkowitz is an Assistant Professor in the Brown University Computer Science Department interested in graph, online and approximation algorithms as well as metric embeddings. He completed his PhD at Carnegie Mellon and did a postdoc at ETH Zurich.