Vi beskriver en (1+ε) - approximation algoritm för att hitta den minsta distorsion inbäddning av en n-punkt metriska utrymme X i den kortaste vägen metriska utrymmet för en viktad graf G med m hörn. Löptiden för vår algoritm parametriseras av värdena för den minsta distorsion, δ opt, spridningen,  på punkterna i X, trädbredden, G, och dubbleringsdimensionen, λ, av G. I synnerhet, vårt resultat innebär en PTAS en X med polynom spridning, och dubblering dimension av G, trädbredden av G, och δ opt, är alla konstanta. Till exempel, om X har en polynom spridning och δ opt är en konstant, vi få PTAS's för att inbädda X i följande utrymmen: linjen, en cykel, en begränsad grad oviktat träd, och en begränsad grad oviktad k-outer planar graf (för en konstant k).
I ett mycket nyligen verk Nayyeri och Raichel REF erhöll en (1 + ε) - approximation algoritm för att hitta den minsta distortion inbäddning av en n-punkt metrisk utrymme M i den kortaste vägen metriska utrymmet för en viktad graf H med m hörn.
A Treehouse with Custom Windows: Minimum Distortion Embeddings into Bounded Treewidth Graphs
{'venue': 'SODA', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}