Suppose we are given a weighted graph which defines a shortest-path metric space with small doubling dimension. Can we represent this metric space by an unweighted graph of small doubling dimension? Since unweighted graphs are simpler (and easier to design algorithms for), such a representation may be useful.
However, the simplest idea of subdividing edges to create an unweighted graph may cause the dimension to increase unboundedly. We will show that such a representation exists if we allow distances to change by a $(1+eps)$ factor, such the dimension is maintained to within a $O(log 1/eps)$ factor, independent of the size of the underlying graph.
This is joint work with Kunal Talwar.
Copyright. All Rights Reserved.