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

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

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

Project

<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>

Continuities

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

Publication year

2018

Confidentiality

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

Name of the periodical

SIAM Journal on Computing

ISSN

0097-5397

e-ISSN

—

Volume of the periodical

47

Issue of the periodical within the volume

4

Country of publishing house

US - UNITED STATES

Number of pages

38

Pages from-to

1667-1704

UT code for WoS article

000443195600014

EID of the result in the Scopus database

2-s2.0-85053622675