Hardness of Embedding Metric Spaces of Equal Size

DOI10.1007/978-3-540-74208-1_16zbMath1171.68871OpenAlexW1725762450MaRDI QIDQ3603467

Subhash A. 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) Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Metric spaces, metrizability (54E35) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Approximation algorithms (68W25)

Related Items

Pattern matching in doubling spaces ⋮ Logic of confidence ⋮ Knowing-how under uncertainty ⋮ Unnamed Item ⋮ Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces