Showing cs.DSShow all
3 papers · 1 filter
cs.DS2004★ 272 cited
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…
cs.DS2004★ 17 cited
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…
cs.DS2004★ 67 cited
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…