Volume in general metric spaces
Planar graphs; geometric and topological aspects of graph theory (05C10) Signed and weighted graphs (05C22) Graph algorithms (graph-theoretic aspects) (05C85) Metric spaces, metrizability (54E35) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
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)\).
- A Best Possible Heuristic for the k-Center Problem
- Advances in metric embedding theory
- Approximating the bandwidth via volume respecting embeddings
- Clustering to minimize the maximum intercluster distance
- Compact routing with slack
- Compact routing with slack in low doubling dimension
- Dynamic Steiner Tree Problem
- Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion
- scientific article; zbMATH DE number 5506210 (Why is no real title available?)
- scientific article; zbMATH DE number 1833416 (Why is no real title available?)
- Improved bandwidth approximation for trees and chordal graphs
- Measured descent: A new embedding method for finite metrics
- Metric embeddings -- beyond one-dimensional distortion
- New length bounds for cycle bases
- On average distortion of embedding metrics into the line and into l₁
- On Lipschitz embedding of finite metric spaces in Hilbert space
- Spanners with Slack
- Triangulation and embedding using small sets of beacons
- Volume in general metric spaces
- Volume distortion for subsets of Euclidean spaces
- On notions of distortion and an almost minimum spanning tree with constant average distortion
- Volumes of Generalized Unit Balls
- Volume in general metric spaces
- scientific article; zbMATH DE number 6166904 (Why is no real title available?)
- On multiplicative \(\lambda\)-approximations and some geometric applications
This page was built for publication: Volume in general metric spaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q464741)
