Past Events

Seminar

Scattering and Sparse Partitions, and their Applications

 

Download as iCal file

Wednesday, February 05, 2020, 11:00am - 12:00pm

 

Rutgers/DIMACS Theory of Computing Seminar

Speaker: Arnold Filtser (Columbia)

Location : CoRE 301

Event Type: Seminar

Abstract: A partition P of a weighted graph G is (sigma, tau, Delta)-sparse if every cluster has diameter at most Delta, and every ball of radius Delta/sigma intersects at most tau clusters. Similarly, P is (sigma, tau, Delta)-scattering if instead for balls we require that every shortest path of length at most Delta/sigma intersects at most tau clusters. Given a graph G that admits a (sigma, tau, Delta)-sparse partition for all Delta>0, Jia et al. [STOC05] constructed a solution for the Universal Steiner Tree problem (and also Universal TSP) with stretch O(tau sigma^2 log_tau n). Given a graph G that admits a (sigma, tau, Delta)-scattering partition for all Delta>0, we construct a solution for the Steiner Point Removal problem with stretch O( tau^3 sigma^3). We then construct sparse and scattering partitions for various different graph families, receiving new results for the Universal Steiner Tree and Steiner Point Removal problems.