A (1+epsilon)-EMBEDDING OF LOW HIGHWAY DIMENSION GRAPHS INTO BOUNDED TREEWIDTH GRAPHS

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10386940" target="_blank" >RIV/00216208:11320/18:10386940 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1137/16M1067196" target="_blank" >https://doi.org/10.1137/16M1067196</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/16M1067196" target="_blank" >10.1137/16M1067196</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A (1+epsilon)-EMBEDDING OF LOW HIGHWAY DIMENSION GRAPHS INTO BOUNDED TREEWIDTH GRAPHS

Popis výsledku v původním jazyce

Graphs with bounded highway dimension were introduced by Abraham et al. [Proceedings of SODA 2010, pp. 782-793] as a model of transportation networks. We show that any such graph can be embedded into a distribution over bounded treewidth graphs with arbitrarily small distortion. More concretely, given a weighted graph G = (V, E) of constant highway dimension, we show how to randomly compute a weighted graph H = (V, E&apos;) that distorts shortest path distances of G by at most a 1 + E factor in expectation, and whose treewidth is polylogarithmic in the aspect ratio of G. Our probabilistic embedding implies quasi -polynomial time approximation schemes for a number of optimization problems that naturally arise in transportation networks, including Travelling Salesman, Steiner Tree, and Facility Location. To construct our embedding for low highway dimension graphs we extend Talwar&apos;s [Proceedings of STOC 2004, pp. 281-290] embedding of low doubling dimension metrics into bounded treewidth graphs, which generalizes known results for Euclidean metrics. We add several nontrivial ingredients to Talwar&apos;s techniques, and in particular thoroughly analyze the structure of low highway dimension graphs. Thus we demonstrate that the geometric toolkit used for Euclidean metrics extends beyond the class of low doubling metrics.

Název v anglickém jazyce

A (1+epsilon)-EMBEDDING OF LOW HIGHWAY DIMENSION GRAPHS INTO BOUNDED TREEWIDTH GRAPHS

Popis výsledku anglicky

Graphs with bounded highway dimension were introduced by Abraham et al. [Proceedings of SODA 2010, pp. 782-793] as a model of transportation networks. We show that any such graph can be embedded into a distribution over bounded treewidth graphs with arbitrarily small distortion. More concretely, given a weighted graph G = (V, E) of constant highway dimension, we show how to randomly compute a weighted graph H = (V, E&apos;) that distorts shortest path distances of G by at most a 1 + E factor in expectation, and whose treewidth is polylogarithmic in the aspect ratio of G. Our probabilistic embedding implies quasi -polynomial time approximation schemes for a number of optimization problems that naturally arise in transportation networks, including Travelling Salesman, Steiner Tree, and Facility Location. To construct our embedding for low highway dimension graphs we extend Talwar&apos;s [Proceedings of STOC 2004, pp. 281-290] embedding of low doubling dimension metrics into bounded treewidth graphs, which generalizes known results for Euclidean metrics. We add several nontrivial ingredients to Talwar&apos;s techniques, and in particular thoroughly analyze the structure of low highway dimension graphs. Thus we demonstrate that the geometric toolkit used for Euclidean metrics extends beyond the class of low doubling metrics.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2018

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

SIAM Journal on Computing

ISSN

0097-5397

e-ISSN

—

Svazek periodika

47

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

38

Strana od-do

1667-1704

Kód UT WoS článku

000443195600014

EID výsledku v databázi Scopus

2-s2.0-85053622675