272 citations · 652 across the 10 of their papers we have counts for
6 papers · 1 filter
Measured descent: A new embedding method for finite metrics
Robert Krauthgamer, James R. Lee, Manor Mendel +1
We devise a new embedding technique, which we call measured descent, based on decomposing a metric space locally, at varying speeds, according to the density of some probability me…
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…
Multi-Embedding of Metric Spaces
Yair Bartal, Manor Mendel
Metric embedding has become a common technique in the design of algorithms. Its applicability is often dependent on how high the embedding's distortion is. For example, embedding f…
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…
Better algorithms for unfair metrical task systems and applications
Amos Fiat, Manor Mendel
Unfair metrical task systems are a generalization of online metrical task systems. In this paper we introduce new techniques to combine algorithms for unfair metrical task systems…
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…