Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1
share
We prove that there is a randomized polynomial-time algorithm that given an edge-weighted graph G excluding a fixed-minor Q on n vertices and an accuracy parameter ε>0, constructs an edge-weighted graph H and an embedding η V(G)→ V(H) with the following properties: * For any constant size Q, the treewidth of H is polynomial in ε^-1, log n, and the logarithm of the stretch of the distance metric in G. * The expected multiplicative distortion is (1+ε): for every pair of vertices u,v of G, we have dist_H(η(u),η(v))≥dist_G(u,v) always and Exp[dist_H(η(u),η(v))]≤ (1+ε)dist_G(u,v). Our embedding is the first to achieve polylogarithmic treewidth of the host graph and comes close to the lower bound by Carroll and Goel, who showed that any embedding of a planar graph with 𝒪(1) expected distortion requires the host graph to have treewidth Ω(log n). It also provides a unified framework for obtaining randomized quasi-polynomial-time approximation schemes for a variety of problems including network design, clustering or routing problems, in minor-free metrics where the optimization goal is the sum of selected distances. Applications include the capacitated vehicle routing problem, and capacitated clustering problems.
READ FULL TEXT