125 citations · 360 across the 21 of their papers we have counts for
21 papers
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…
Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces
Lee-Ad Gottlieb, Yair Bartal
We give an algorithm that computes a -approximate Steiner forest in near-linear time . This is a dramatic improvement upon the…