Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1*
Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1*
复制标题
平面和无次要度量嵌入到多对数树宽度量中，预期乘性失真任意接近 1*
DOI：
--
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Michal Pilipczuk
中科院分区：
文献类型：
--
作者：
Vincent Cohen;Hung Le;Marcin Pilipczuk;Michal Pilipczuk
我们证明了存在一个随机多项式时间算法，它给出一个不含n个顶点的固定子项q的边加权图G和一个精度参数$varepsilongt$0，构造一个边加权图H和一个嵌入的$eta：v(G)。
具有以下性质的右行V(H)$：·对于任意大小的q，H的树宽是$varepsilon^{-1}中的多项式，logn$，以及G中距离度量的伸展的对数。·预期的乘法失真是$(1+varepsilon)$：对于G的每一对顶点$u，v$，我们有$操作符名称{dist}_{H}(eta(U)，eta(V))几何斜运算符名称{dist}_{G}(u，v)$Always和$mathbb{E}left[操作符名称{dist}_{H}(eta(U)，eta(V))]埃塔(V))
[leqslant(1+varepsilon)操作符名称{dist}_{G}(u，v)$.我们的嵌入首次实现了宿主图的多对数树宽，并接近Carroll和Goel的下界，后者证明了任何具有$Mathcal{O}(1)$预期失真的平面图的嵌入都要求宿主图具有树宽$omega(Logn)$。它还提供了一个统一的框架来获得各种问题的随机准多项式时间近似方案，包括网络设计、集群或路由问题，其中优化目标是所选距离的和。应用包括有能力的车辆路径问题和有能力的集群问题。
We prove that there is a randomized polynomialtime algorithm that given an edge-weighted graph G excluding a fixed-minor Q on n vertices and an accuracy parameter $varepsilongt$ 0, constructs an edge-weighted graph H and an embedding $eta: V(G)
ightarrow V(H)$ with the following properties:•For any constant size Q, the treewidth of H is polynomial in $varepsilon^{-1}, log n$, and the logarithm of the stretch of the distance metric in G.•The expected multiplicative distortion is $(1+varepsilon)$: for every pair of vertices $u, v$ of G, we have $operatorname{dist}_{H}(eta(u), eta(v)) geqslant operatorname{dist}_{G}(u, v)$ always and $mathbb{E}left[operatorname{dist}_{H}(eta(u), eta(v))
ight] leqslant(1+varepsilon) operatorname{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 $mathcal{O}(1)$ expected distortion requires the host graph to have treewidth $Omega(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.
平面和次要自由度量的低树宽嵌入
DOI：
10.1109/focs54457.2022.00105
发表时间：
2022
期刊：
The 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022
影响因子：
--
作者：
Filtser, Arnold;Le, Hung
通讯作者：
Le, Hung
将平面图嵌入到低树宽图中，并应用于度量问题的高效近似方案
DOI：
10.1137/1.9781611975482.66
发表时间：
2019
期刊：
Proceedings of the Thirtieth Annual {ACM-SIAM} Symposium on Discrete Algorithms
影响因子：
--
作者：
Eli Fox-Epstein, Eli
Klein
通讯作者：
Eli Fox-Epstein, Eli
Klein