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)

• 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
• scientific article; zbMATH DE number 2079382 (Why is no real title available?)
• Inapproximability for metric embeddings into $\mathbb{R}^{d}$
• Logic of confidence
• Approximation algorithms for low-distortion embeddings into low-dimensional spaces
• Inapproximability for planar embedding problems
• 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)