Hardness of Embedding Metric Spaces of Equal Size
DOI10.1007/978-3-540-74208-1_16zbMATH Open1171.68871OpenAlexW1725762450MaRDI QIDQ3603467FDOQ3603467
Authors: Subhash Khot, Rishi Saket 
Publication date: 17 February 2009
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-74208-1_16
Recommendations
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Metric spaces, metrizability (54E35)
Cited In (14)
- Hard metrics from Cayley graphs of abelian groups
- Pattern matching in doubling spaces
- Knowing-how under uncertainty
- Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces
- Paper Retraction: On the Hardness of Embeddings Between Two Finite Metrics
- Automata, Languages and Programming
- Low distortion metric embedding into constant dimension
- Title not available (Why is that?)
- Inapproximability for metric embeddings into $\mathbb{R}^{d}$
- Logic of confidence
- Inapproximability for planar embedding problems
- Approximation algorithms for low-distortion embeddings into low-dimensional spaces
- Hard Metrics from Cayley Graphs of Abelian Groups
- Labelings vs. embeddings: on distributed and prioritized representations of distances
This page was built for publication: Hardness of Embedding Metric Spaces of Equal Size
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3603467)
