Polylogarithmic Universal Steiner Trees and Strong Sparse Partition Hierarchies

Polylogarithmic Universal Steiner Trees and Strong Sparse Partition Hierarchies (via Zoom)

Abstract: This talk is concerned with 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. 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.