Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

On Sparse Partitions
event speaker icon
Arnold Filtser (Bar-Ilan university)
event date icon
Wednesday, 24.07.2024, 12:45
event location icon
Amado 814

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 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 applications to: Universal TSP, Steiner point removal, universal Steiner tree, and facility location.