A (1+{\varepsilon }) ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
From MaRDI portal
Publication:3448808
Abstract: Graphs with bounded highway dimension were introduced by Abraham et al. [SODA 2010] 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') that distorts shortest path distances of G by at most a 1 + 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's [STOC 2004] embedding of low doubling dimension metrics into bounded treewidth graphs, which generalizes known results for Euclidean metrics. We add several non-trivial ingredients to Talwar's techniques, and in particular thoroughly analyse 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.
Recommendations
- A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
- Embeddings of graphs of fixed treewidth and bounded degree
- Embedding Graphs with Bounded Treewidth into Their Optimal Hypercubes
- Embedding graphs with bounded treewidth into optimal hypercubes
- Embedding planar graphs into low-treewidth graphs with applications to efficient approximation schemes for metric problems
- Embeddings of \(k\)-connected graphs of pathwidth \(k\)
- scientific article; zbMATH DE number 1617252
- Embedding Bounded Bandwidth Graphs into ℓ1
- Tight lower bounds on graph embedding problems
- Tight bounds for embedding bounded degree trees
Cites work
- scientific article; zbMATH DE number 6381762 (Why is no real title available?)
- scientific article; zbMATH DE number 2089220 (Why is no real title available?)
- scientific article; zbMATH DE number 5734726 (Why is no real title available?)
- scientific article; zbMATH DE number 1754594 (Why is no real title available?)
- scientific article; zbMATH DE number 1775394 (Why is no real title available?)
- scientific article; zbMATH DE number 1775400 (Why is no real title available?)
- scientific article; zbMATH DE number 6783450 (Why is no real title available?)
- A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
- A tight bound on approximating arbitrary metrics by tree metrics
- Approximation schemes for NP-hard geometric optimization problems: a survey
- Bypassing the embedding
- Fast Routing in Road Networks with Transit Nodes
- Graph minors. II. Algorithmic aspects of tree-width
- Greedy Strikes Back: Improved Facility Location Algorithms
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- Highway dimension and provably efficient shortest path algorithms
- Highway dimension, shortest paths, and provably efficient algorithms
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
- VC-dimension and shortest path algorithms
Cited in
(9)- Active nearest-neighbor learning in metric spaces
- Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
- A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
- On the VC-dimension of unique round-trip shortest path systems
- Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
- Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension
- Fixed parameter approximations for \(k\)-center problems in low highway dimension graphs
- Travelling on graphs with small highway dimension
- The parameterized hardness of the \(k\)-center problem in transportation networks
This page was built for publication: A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448808)
