论文标题
Gap-Eth紧密近似计划，用于红绿蓝色分离和双色非交叉的欧几里得旅行者旅行
Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing Euclidean Travelling Salesman Tours
论文作者
论文摘要
在本文中，我们研究通过非交叉结构连接点类别的问题。给定一组彩色终端点，我们希望找到每种颜色的图形，该图将其颜色的所有终端连接到没有两个图形相互交叉的限制。我们在欧几里得平面和平面图上都考虑了这些问题。 在算法方面，我们为两色旅行者问题以及红蓝色绿色的分离问题提供了一个间隙 - 埃及电密性EPTA（我们希望将三种颜色的终端分开，两种颜色的终端具有两个最小长度的非交叉多边形）。这改善了Arora和Chang（ICALP 2003）的工作，他们为更简单的红蓝色分离问题提供了较慢的PTA。对于未加权的平面图，我们还为两色旅行推销员问题展示了PTA。所有这些结果均基于我们可能具有独立关注的新修补程序。 在负面，我们表明，将终端对与非交叉路径连接的问题是欧几里得平面上的NP-HARD，并且在平面图中找到两个非交叉跨越树的问题是NP-HARD。
In this paper, we study problems of connecting classes of points via noncrossing structures. Given a set of colored terminal points, we want to find a graph for each color that connects all terminals of its color with the restriction that no two graphs cross each other. We consider these problems both on the Euclidean plane and in planar graphs. On the algorithmic side, we give a Gap-ETH-tight EPTAS for the two-colored traveling salesman problem as well as for the red-blue-green separation problem (in which we want to separate terminals of three colors with two noncrossing polygons of minimum length), both on the Euclidean plane. This improves the work of Arora and Chang (ICALP 2003) who gave a slower PTAS for the simpler red-blue separation problem. For the case of unweighted plane graphs, we also show a PTAS for the two-colored traveling salesman problem. All these results are based on our new patching procedure that might be of independent interest. On the negative side, we show that the problem of connecting terminal pairs with noncrossing paths is NP-hard on the Euclidean plane, and that the problem of finding two noncrossing spanning trees is NP-hard in plane graphs.
