Arnold Filtser, Bar-Ilan University

Abstract

A partition $mathcal{P}$ of a metric space $(X,d_X)$ is $(sigma,tau,Delta)$-sparse if each cluster has a diameter at most $Delta$, and every ball with of radius $Delta/sigma$ intersects at most $tau$ clusters. In this talk, we will explore the construction and different applications of sparse partitions in their various forms over the years. As time allows, we will discuss: universal TSP, Steiner point removal, universal Steiner tree, and facility location.

[Video]