Title: Prioritized Metric Structures and Embedding
Authors: Michael Elkin, Arnold Filtser and Ofer Neiman.
Abstract: Metric data structures (distance oracles, distance labeling schemes, routing schemes) and low-distortion embeddings provide a powerful
algorithmic methodology, which has been successfully applied for approximation algorithms, online algorithms,
distributed algorithms and for computing sparsifiers.
However, this methodology appears to have a limitation: the worst-case performance inherently depends on the cardinality of the metric,
and one could not specify in advance which vertices/points should enjoy a better
service (i.e., stretch/distortion, label size/dimension) than that given by the worst-case guarantee.
In this paper we alleviate this limitation by devising a suit of {\em prioritized} metric data structures and embeddings.
We show that given a priority ranking $(x_1,x_2,...,x_n)$ of the graph vertices (respectively, metric points) one can devise a metric
data structure (respectively, embedding) in which the stretch (resp., distortion) incurred by any pair containing a vertex $x_j$ will
depend on the rank $j$ of the vertex. We also show that other important parameters, such as the label size and (in some sense) the dimension,
may depend only on $j$. In some of our metric data structures (resp., embeddings) we achieve both prioritized stretch (resp., distortion) and
label size (resp., dimension) {\em simultaneously}. The worst-case performance of our metric data structures and embeddings is typically
asymptotically no worse than of their non-prioritized counterparts.