论文标题
平面和无少量指标的低树宽嵌入
Low Treewidth Embeddings of Planar and Minor-Free Metrics
论文作者
论文摘要
Cohen-Addad，Filtser，Klein和Le [focs'20]构建了一个随机嵌入直径$ d $的次要图形$ d $的随机嵌入到TreeWidth $o_ε（\ log log n）$的图形中，并带有预期的加性失真$++εd$。 Cohen-Addad等。然后使用嵌入式设计用于电容的车辆路由问题的第一个准多项式时间近似方案（QPTA）。 Filtser和Le [Stoc'21]使用嵌入（以不同的方式）为公制贝克在少量图中的问题设计QPTA。在这项工作中，我们设计了一种新的嵌入技术，以改善Cohen-Addad等人的树宽结合。指数为$o_ε（\ log \ log n）^2 $。作为推论，我们获得了第一个在少量图中的电容车辆路由问题的有效PTA。我们还显着改善了QPTA的运行时间，用于公制的Baker在次要图中的问题，从$ n^{o_ε（\ log（n））} $到$ n^{o_ε（\ log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log（n）） 将我们的嵌入技术应用于平面图上，我们获得了直径$ d $平面图的确定性嵌入到TreeWidth $ o（（（\ log \ log \ log n）^2）/ε）/ε）$和添加性失真$+εd$中的确定性嵌入。我们结果的重要推论包括用于公制面包师问题的双晶型PTA，以及用于平面图中有界能力的车辆路由问题的PTA，两者都在几乎是线性的时间内运行。我们的算法的运行时间明显优于需要二次时间的以前算法。 我们嵌入中的一个关键想法是用TreeWidth $ O（\ log \ log n）$和Hop-Diameter $ O（\ log \ log \ log n）$构建（精确的）仿真器。该结果可能具有独立的利益。
Cohen-Addad, Filtser, Klein and Le [FOCS'20] constructed a stochastic embedding of minor-free graphs of diameter $D$ into graphs of treewidth $O_ε(\log n)$ with expected additive distortion $+εD$. Cohen-Addad et al. then used the embedding to design the first quasi-polynomial time approximation scheme (QPTAS) for the capacitated vehicle routing problem. Filtser and Le [STOC'21] used the embedding (in a different way) to design a QPTAS for the metric Baker's problems in minor-free graphs. In this work, we devise a new embedding technique to improve the treewidth bound of Cohen-Addad et al. exponentially to $O_ε(\log\log n)^2$. As a corollary, we obtain the first efficient PTAS for the capacitated vehicle routing problem in minor-free graphs. We also significantly improve the running time of the QPTAS for the metric Baker's problems in minor-free graphs from $n^{O_ε(\log(n))}$ to $n^{O_ε(\log\log(n))^3}$. Applying our embedding technique to planar graphs, we obtain a deterministic embedding of planar graphs of diameter $D$ into graphs of treewidth $O((\log\log n)^2)/ε)$ and additive distortion $+εD$ that can be constructed in nearly linear time. Important corollaries of our result include a bicriteria PTAS for metric Baker's problems and a PTAS for the vehicle routing problem with bounded capacity in planar graphs, both run in almost-linear time. The running time of our algorithms is significantly better than previous algorithms that require quadratic time. A key idea in our embedding is the construction of an (exact) emulator for tree metrics with treewidth $O(\log\log n)$ and hop-diameter $O(\log \log n)$. This result may be of independent interest.
