Volume in general metric spaces (Q464741)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Volume in general metric spaces |
scientific article |
Statements
Volume in general metric spaces (English)
0 references
29 October 2014
0 references
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)\).
0 references
metric embedding
0 references
volume preserving embedding
0 references