Approximating the bandwidth via volume respecting embeddings

DOI10.1006/jcss.1999.1682zbMath0958.68191OpenAlexW2080608361MaRDI QIDQ1577009

Uriel Feige

Publication date: 27 August 2000

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/6d39860116554a6c08506553db7e2d93efe3e040

zbMATH Keywords

small distortion embeddingsvolume respecting embeddings

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items

Convex Relaxations for Permutation Problems, Faster Exact Bandwidth, Limitations to Fréchet's metric embedding method, Approximating the bandwidth of caterpillars, Graph bandwidth of weighted caterpillars, Unnamed Item, Compact representation of graphs with bounded bandwidth or treedepth, An exponential time 2-approximation algorithm for bandwidth, Hardness results for approximating the bandwidth, Complexity and Algorithms for Well-Structured k-SAT Instances, Delone sets that are not rectifiable under Lipschitz co-uniformly continuous bijections, Interval degree and bandwidth of a graph, Optimal distortion embedding of complete binary trees into lines, Algorithms for graphs with small octopus, Volume in general metric spaces, Cellular resolutions of cointerval ideals, On the 3-distortion of a path, Combinatorial theorems about embedding trees on the real line, Labeling schemes for weighted dynamic trees, The intrinsic dimensionality of graphs, Line-distortion, bandwidth and path-length of a graph, On the graph turnpike problem, Mapping \(n\) grid points onto a square forces an arbitrarily large Lipschitz constant, Volume distortion for subsets of Euclidean spaces, Retracting Graphs to Cycles, An Exponential Time 2-Approximation Algorithm for Bandwidth, Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces, The legacy of Jean Bourgain in geometric functional analysis, Unnamed Item, Moderately exponential time and fixed parameter approximation algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The bandwidth problem and operations on graphs
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• On Lipschitz embedding of finite metric spaces in Hilbert space
• Graphs with small bandwidth and cutwidth
• The Johnson-Lindenstrauss lemma and the sphericity of some graphs
• The NP-completeness of the bandwidth minimization problem
• The geometry of graphs and some of its algorithmic applications
• Beyond NP-completeness for problems of bounded width (extended abstract)
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• Computing the Bandwidth of Interval Graphs
• On the Probable Performance of Heuristics for Bandwidth Minimization
• The bandwidth problem for graphs and matrices—a survey
• The Bandwidth of Caterpillars with Hairs of Length 1 and 2
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Bandwidth Minimization: An approximation algorithm for caterpillars
• Complexity Results for Bandwidth Minimization
• Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
• Approximating the bandwidth for asteroidal triple-free graphs