Embedding into \(l_{\infty }^{2}\) is easy, embedding into \(l_{\infty}^{3}\) is NP-complete
type: Item
instance of: scholarly article
title: Embedding into \(l_{\infty }^{2}\) is easy, embedding into \(l_{\infty}^{3}\) is NP-complete
zbMATH Open document ID: 1149.68075
author: Jeff Edmonds
published in: Discrete \& Computational Geometry
publication date: 2008-08-19T00:00:00Z
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 51K05
zbMATH DE Number: 5313113
zbMATH Keywords: Embedding
zbMATH Keywords: Algorithm
zbMATH Keywords: NP-complete
zbMATH Keywords: Metric space
zbMATH Keywords: Möbius
MaRDI profile type: Publication
full work available at URL: s00454-008-9064-z
OpenAlex ID: W1985603099
cites work: The cut cone,L1 embeddability, complexity, and multicommodity flows
cites work: Q4471326
cites work: Embedding metric spaces in the rectilinear plane: a six-point criterion
cites work: Embedding into the rectilinear grid
cites work: Embedding into rectilinear spaces
cites work: Q5818996
cites work: Geometry of cuts and metrics
cites work: Randomized fully dynamic graph algorithms with polylogarithmic time per operation
cites work: A bounded compactness theorem for \(L^ 1\)-embeddability of metric spaces in the plane
DOI: 10.1007/S00454-008-9064-Z
Recommended article: Q2934634
Recommended article: Embeddability in $\mathbb{R}^3$ is NP-hard
Recommended article: Embeddability in R 3 is NP-hard
Recommended article: Q4633898
Recommended article: Hardness of embedding simplicial complexes in \(\mathbb R^d\)
Recommended article: Hardness of almost embedding simplicial complexes in \(\mathbb {R}^d\)
Recommended article: The embedding \(O(2m,2^ k)\leq Sp(2m,2^ k)\)
Recommended article: Automata, Languages and Programming
Recommended article: Geometric complexity of embeddings in \(\mathbb R^d\)
Recommended article: Embeddability of Simplicial Complexes is Undecidable
description: scientific article; zbMATH DE number 5313113