Parallel Probabilistic Tree Embeddings, K-Median, and Buy-at-Bulk Network Design

Date Added: Jun 2012
Format: PDF

The idea of embedding a finite metric into a distribution of "Simpler" metrics has proved to be a useful and versatile technique in the algorithmic study of metric spaces, with far-reaching consequences to understanding finite metrics and developing approximation algorithms. This paper presents parallel algorithms for embedding an arbitrary n-point metric space into a distribution of dominating trees with O(log n) expected stretch. Such embedding has proved useful in the design of many approximation algorithms in the sequential setting.