2023/04/14 by Cohen-Addad, Vincent, Le, Hung, Pilipczuk, Marcin +1 · 1 citation
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2304.07268
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 η\colon 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 distH(η(u),η(v))≥ distG(u,v) always and Exp[distH(η(u),η(v))]≤ (1+ε)distG(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 O(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.