Advertisement
Published in:
2011 | OriginalPaper | Chapter
Bandwidth and Low Dimensional Embedding
Authors : Yair Bartal, Douglas E. Carroll, Adam Meyerson, Ofer Neiman
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We design an algorithm to embed graph metrics into ℓ
p
with dimension and distortion both dependent only upon the bandwidth of the graph. In particular we show that any graph of bandwidth
k
embeds with distortion polynomial in
k
into
O
(log
k
) dimensional ℓ
p
, 1 ≤
p
≤ ∞. Prior to our result the only known embedding with distortion independent of
n
was into high dimensional ℓ
1
and had distortion exponential in
k
. Our low dimensional embedding is based on a general method for reducing dimension in an ℓ
p
embedding, satisfying certain conditions, to the intrinsic dimension of the point set, without substantially increasing the distortion. As we observe that the family of graphs with bounded bandwidth are doubling, our result can be viewed as a positive answer to a conjecture of Assouad [2], limited to this family. We also study an extension to graphs of bounded tree-bandwidth.