A (1+{\varepsilon }) ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs

DOI10.1007/978-3-662-47672-7_38zbMATH Open1398.68671arXiv1502.04588OpenAlexW2203654255MaRDI QIDQ3448808FDOQ3448808

Authors: Andreas Emil Feldmann, Wai Shing Fung, Jochen Könemann, Ian Post 

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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 + $varepsilon$ 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.

Full work available at URL: https://arxiv.org/abs/1502.04588

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\)
• Publication:2721972
• Embedding Bounded Bandwidth Graphs into ℓ1
• Tight lower bounds on graph embedding problems
• Tight bounds for embedding bounded degree trees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Transportation, logistics and supply chain management (90B06)

Cites Work

• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Greedy Strikes Back: Improved Facility Location Algorithms
• Title not available (Why is that?)
• The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
• Graph minors. II. Algorithmic aspects of tree-width
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• A tight bound on approximating arbitrary metrics by tree metrics
• VC-dimension and shortest path algorithms
• Highway dimension, shortest paths, and provably efficient algorithms
• Title not available (Why is that?)
• Approximation schemes for NP-hard geometric optimization problems: a survey
• Fast Routing in Road Networks with Transit Nodes
• A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
• Bypassing the embedding
• Title not available (Why is that?)
• Title not available (Why is that?)
• Highway dimension and provably efficient shortest path algorithms
• Title not available (Why is that?)

Cited In (9)

• Fixed parameter approximations for \(k\)-center problems in low highway dimension graphs
• On the VC-dimension of unique round-trip shortest path systems
• The parameterized hardness of the \(k\)-center problem in transportation networks
• Active nearest-neighbor learning in metric spaces
• Travelling on graphs with small highway dimension
• 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
• 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

Uses Software

• DIMACS

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)