125 citations · 360 across the 21 of their papers we have counts for
11 papers · 1 filter
Improved fixed-parameter bounds for Min-Sum-Radii and Diameters -clustering and their fair variants
Sandip Banerjee, Yair Bartal, Lee-Ad Gottlieb +1
We provide improved upper and lower bounds for the Min-Sum-Radii (MSR) and Min-Sum-Diameters (MSD) clustering problems with a bounded number of clusters . In particular, we prop…
Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds
Yair Bartal, Ora N. Fandina, Seeun William Umboh
Probabilistic metric embedding into trees is a powerful technique for designing online algorithms. The standard approach is to embed the entire underlying metric into a tree metric…
Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures
Yair Bartal, Ora Nova Fandina, Kasper Green Larsen
It is well known that the Johnson-Lindenstrauss dimensionality reduction method is optimal for worst case distortion. While in practice many other methods and heuristics are used,…
Advances in Metric Ramsey Theory and its Applications
Yair Bartal
Metric Ramsey theory is concerned with finding large well-structured subsets of more complex metric spaces. For finite metric spaces this problem was first studies by Bourgain, Fig…
Covering Metric Spaces by Few Trees
Yair Bartal, Nova Fandina, Ofer Neiman
A {\em tree cover} of a metric space is a collection of trees, so that every pair has a low distortion path in one of the trees. If it has the stronger property…
On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion
Yair Bartal, Arnold Filtser, Ofer Neiman
This paper makes two main contributions: The first is the construction of a near-minimum spanning tree with constant average distortion. The second is a general equivalence theorem…