Date/Time
Date(s) - 08/11/2024
11:00 am - 12:00 pm

Location: Zoom

Speaker: Dr. Ofer Neiman (David Ben-Gurion University)

Title: Covering Metric Spaces by Few Trees

Abstract: A tree cover of a metric space (X,d) is a collection of trees, so that every pair x,y ? X has a low distortion path in one of the trees. If it has the stronger property that every point x ? X has a single tree with low distortion paths to all other points, we call this a Ramsey tree cover.

We devise efficient algorithms to construct tree covers and Ramsey tree covers for general, planar and doubling metrics. We pay particular attention to the desirable case of distortion close to 1, and study what can be achieved when the number of trees is small. In particular, our work shows a large separation between what can be achieved by tree covers vs. Ramsey tree covers.

This is joint work with Yair Bartal and Nova Fandina.