Volume in general metric spaces (Q464741)

The authors are concerned with Feige's notion of volume and with volume preserving embeddings. They generalize an inequality of Feige regarding an \(n\) point metric space and obtain the following corollary: Given a complete weighted graph with arbitrary weights which are at least \(2\), the greedy algorithm is \(O\)(1)-competitive for the online metric Steiner tree with logarithmic edge costs. One of their main results on volume preserving embeddings is the following theorem: For any metric space \((X,d)\) on \(n\) points and any \(2 \leq k \leq n\) there is a map \(f:X\rightarrow L_2\) such that for any \(1 \leq q \leq \infty\), \(\operatorname{dist}_q^{(k-1)}(f) \in O(\min\{\lceil q/(k-1) \rceil\cdot \log k, \log n\})\). In particular, \(\text{dist}_{\infty}^{(k-1)}\in O(\log n)\) and \(\operatorname{dist}_1^{(k-1)}(f) \in O(\log k)\).