Mathematics – Metric Geometry
Scientific paper
2010-07-03
Mathematics
Metric Geometry
27 pages, 4 figires, extended abstract to appear in the proceedings of APPROX-RANDOM 2010
Scientific paper
In this paper, we present a simple factor 6 algorithm for approximating the optimal multiplicative distortion of embedding a graph metric into a tree metric (thus improving and simplifying the factor 100 and 27 algorithms of B\v{a}doiu, Indyk, and Sidiropoulos (2007) and B\v{a}doiu, Demaine, Hajiaghayi, Sidiropoulos, and Zadimoghaddam (2008)). We also present a constant factor algorithm for approximating the optimal distortion of embedding a graph metric into an outerplanar metric. For this, we introduce a general notion of metric relaxed minor and show that if G contains an alpha-metric relaxed H-minor, then the distortion of any embedding of G into any metric induced by a H-minor free graph is at meast alpha. Then, for H=K_{2,3}, we present an algorithm which either finds an alpha-relaxed minor, or produces an O(alpha)-embedding into an outerplanar metric.
Chepoi Victor
Dragan Feodor
Newman Ilan
Rabinovich Yuri
Vaxès Yann
No associations
LandOfFree
Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-402472