Hardness of Embedding Metric Spaces of Equal Size

DOI10.1007/978-3-540-74208-1_16MaRDI QIDQ3603467zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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)

Recommendations

• Inapproximability for metric embeddings into $\mathbb{R}^{d}$
• Approximation algorithms for low-distortion embeddings into low-dimensional spaces
• Automata, Languages and Programming
• Low-distortion embeddings of general metrics into the line
• Inapproximability for planar embedding problems

Cited in

(14)

• Pattern matching in doubling spaces
• Inapproximability for planar embedding problems
• Automata, Languages and Programming
• scientific article; zbMATH DE number 2079382 (Why is no real title available?)
• Hard metrics from Cayley graphs of abelian groups
• Approximation algorithms for low-distortion embeddings into low-dimensional spaces
• Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces
• Paper Retraction: On the Hardness of Embeddings Between Two Finite Metrics
• Hard Metrics from Cayley Graphs of Abelian Groups
• Low distortion metric embedding into constant dimension
• Inapproximability for metric embeddings into $\mathbb{R}^{d}$
• Knowing-how under uncertainty
• Logic of confidence
• 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)