272 citations · 536 across the 6 of their papers we have counts for
6 papers
Fast Construction of Nets in Low Dimensional Metrics, and Their Applications
Sariel Har-Peled, Manor Mendel
We present a near linear time algorithm for constructing hierarchical nets in finite metric spaces with constant doubling dimension. This data-structure is then applied to obtain i…
Metric structures in L_1: Dimension, snowflakes, and average distortion
James R. Lee, Manor Mendel, Assaf Naor
We study the metric properties of finite subsets of L_1. The analysis of such metrics is central to a number of important algorithmic problems involving the cut structure of weight…
Online Companion Caching
Manor Mendel, Steven S. Seiden
This paper is concerned with online caching algorithms for the (n,k)-companion cache, defined by Brehob et. al. In this model the cache is composed of two components: a k-way set-a…
On some low distortion metric Ramsey problems
Yair Bartal, Nathan Linial. Manor Mendel, Assaf Naor
In this note, we consider the metric Ramsey problem for the normed spaces l_p. Namely, given some 1<=p<=infinity and alpha>=1, and an integer n, we ask for the largest m such that…
Euclidean quotients of finite metric spaces
Manor Mendel, Assaf Naor
This paper is devoted to the study of quotients of finite metric spaces. The basic type of question we ask is: Given a finite metric space M, what is the largest quotient of (a sub…
Ramsey-type theorems for metric spaces with applications to online problems
Yair Bartal, Bela Bollobas, Manor Mendel
A nearly logarithmic lower bound on the randomized competitive ratio for the metrical task systems problem is presented. This implies a similar lower bound for the extensively stud…