欧氏平面上Steiner多重圈的拟线性逼近格式

联系我们我 i=1可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）589-601www.elsevier.com/locate/entcs欧氏平面1，2上Steiner多重圈的拟线性逼近格式Carla N. 林茨迈尔数学、计算和认知中心。ABC大学。SantoAndr'e，圣保罗，巴西弗拉维奥·K. 我和法布罗·F。S. EduardoC. Xavier计算研究所。坎皮纳斯大学。坎皮纳斯，圣保罗，巴西摘要我们提出了一个随机逼近方案的欧几里德施泰纳多圈问题，运行准线性时间 在这个问题中，我们给出一个n对点（终端）的集合T =，{ti，t′}，n，欧氏平面，目标是找到一个最小成本的循环集合，使得ti和t′i属于同一个循环，对于每个i1、......、n.这个问题扩展了Steiner循环问题，斯坦纳森林也是斯坦纳树问题的延伸。此外，它还可以应用于取货和送货地点的路由问题关键词：欧氏平面，几何，斯坦纳，逼近算法，拟线性。1介绍Steiner多循环问题是由Pereira等人提出的， 背景下作为Steiner循环问题的自然推广[4]。在这个问题中，我们给出一个完全加权图G，它满足三角不等式和一个终端集{T1，…，Tk}，使得Ti∈V（G），对于每个i∈ [k]：={1，.，k}，并且这些终端集合是成对不相交的。 问题是找到一组顶点不相交1 作 者 感 谢 SaoPauloResear chF 基 金 会 ， FAPES P ， （ gran nts#2015/11937-9 ， #2016/01860-1 ，#2016/23552-7，#2017/22611-2和#2016/21250-3），巴西国家科学技术发展委员会，CNPq，（grants#314366/2018-0，#425340/2016-3和#304856/2017-7）。这该研究部分由巴西N′sauvelSu perior电力公司（CAPES）提供资金，财务代码001。2电子邮件：carla. ufabc.edu.br，fkm@ic.unicamp.br，phablo@ic.unicamp.br，eduardo@ic.unicamp.br3通讯作者。https://doi.org/10.1016/j.entcs.2019.08.0521571-0661/© 2019作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。590C.N. Lintzmayer et al. /Electronic Notes in Theoretical Computer Science 346（2019）589Σ最小成本的循环，使得对于每个i∈[k]，Ti的所有顶点属于同一个循环。可以证明，这简化为每个终端集恰好包含两个终端的问题。在本文中，我们解决的问题限制在欧几里德平面。点x和y之间的线段l = xy的欧几里得距离表示为length（l）。 我们说l是一条以x和y为端点的线段。如果L是线段的多重集，则我们定义ν（L）为L中线段的所有端点的集合，δL（x）为L中以x为端点的线段的个数。另外，L的长度，记作length（L），是l∈Llength（l）。问题1.1欧氏空间多目标问题（ESMC）实例：集合T={{ti，tJ}}n的n对点（a.k.a. 终端）在R2中，欧氏距离ii=1FIND：线段的多重集L，使得对于每个x∈ν（L），δL（x）是偶数每个终端t是L中某条直线的端点，终端对ti和tJi由L中的某个圈连通，对每个i∈[n]。目标：最小化长度（L）。Steiner多圈问题（SMCP）是Steiner圈问题（SCP）的推广，就像Steiner森林推广Steiner树问题一样。 SCP是由Salazar-Gonz′alez提出的，他提出了整数线性规划的多面体研究[5]。Steinov′a证明了有向图中的一般问题不允许有多项式比的近似算法，除非P=NP[6]。她还提出了一个（3/ 2）-近似算法的情况下，输入图是无向和度量。Pereira等人提出了SMCP的度量版本[4]。他们设计了一个4-近似算法和几个算法。在这项工作中，我们提出了一个随机近似计划ESMC运行在O（nlogκn）的时间，其中n表示的数量对终端的输入和κ是一个常数。据我们所知，这是第一个多项式时间近似方案设计的变形施泰纳循环问题。我们的算法结合了Arora[1]为Euclidean TSP引入的一些技术和Borradaile等人[3]为Euclidean Steiner Forest引入的技术。尽管由于ESMC和Euclidean Steneir Forest问题之间的相似性，当处理循环而不是树时，会出现许多额外的复杂性。在所提出的算法中，我们引入了新的思想，并在Borradaile等人提出的策略中进行了一些调整。在动态规划表中，我们通过合并周期访问门户的顺序来使用可行解的不同描述。我们还确保正在构建的解决方案中的点具有偶数度，以便可以构建覆盖这些点的循环。本文的其余部分组织如下。第2节提出了一些最初的和重要的定义，这些定义在整个文本中都是需要的。它还概述了我们的算法是如何工作的。第3节详细说明了我们必须对输入实例执行的一些更改。第四节证明了具有低复杂度的ESMC的ε-近似解的存在性，其中ε是C.N. Lintzmayer et al. /Electronic Notes in Theoretical Computer Science 346（2019）589591在开放区间（0， 1）中为常数。第5节显示了计算这种解的算法的细节。2目录和概述与Arora[1]和Borradaile等人[3]的算法一样，我们的算法也依赖于用直线递归地划分包围终端的空间所提出的算法是一种动态规划，它可以找到一个最优解，该解只在称为门户的特定点上穿过每条这种划分称为解剖，其工作原理如下。最初，我们有一个根剖分正方形，它是一个包含输入实例所有点的边界框。这个根剖分正方形的边长是L，它是2的幂，并且它至少是包围输入的所有端子的最小正方形的边长的两倍。 我们假设这个平方根 初始定位时，其左下角位于平面中的位置（0，0）。因此，每个终端都位于由点（0， 0）和（L/2，L/ 2）定义的正方形内的位置。然后我们随机平移平方根，移动其左下角到位置（-a，-b），其中a和b从范围[0，L/2）中随机均匀选择。这被称为随机移位。平方根及其周围的线被认为是在深度为零。 我们通过将其划分为四个相同面积的正方形来开始对这个平方根的解剖，这是通过切割平方根的水平和垂直解剖线来完成的。因此，这些线和由它们创建的四个正方形的深度为1。对于创建的每个剖分正方形，重复此划分过程，直到每个剖分正方形中只有一个终端（或多个终端，但都具有相同的坐标）。我们说，通过分割一个给定的正方形R而产生的四个正方形是R的子方，R是它们的父方。如果一个剖分正方形R包围另一个剖分正方形RJ，则RJ是R的后代。注意任何正方形的深度都是1加上其父方的深度。这种正方形的嵌套结构形成了四叉树。剖切线的深度l，记为深度（l），定义为l分隔的剖分正方形的最低深度。观察四叉树的叶子的正方形的深度最多为O（logL）。考虑欧氏平面中粒度为1的整数网格，也就是说，将平面划分为边长为1的单元并且其线在整数点处相交的让我成为一条网格线。由于垂直移位的值为L/2，L/2值的水平位移和2i-1这些将使深度（l）=i，我们有P[深度（l）=i] = 2i/L。Borradaile等人[3]提到，对于Steiner森林问题，有必要进一步细分每个剖分正方形，以便在动态规划算法中获得多项式大小的动态编程将单元与门户配对，而不是将终端与门户配对，这将需要指数时间当我们在这里面临同样的问题时，每个解剖正方形进一步细分为一个规则的592C.N. Lintzmayer et al. /Electronic Notes in Theoretical Computer Science 346（2019）589B×B单元格的网格，其中B=O（ε−1）（稍后将精确定义）是2的整数次幂，ε∈（0，1）是常数。该算法构造的解只在剖切线上的指定点处穿过剖分方格的边界，称为门户，这也是降低动态规划复杂性的一种策略。动态程序开始为四叉树的叶子构建解决方案。以自下而上的方式，将四个子剖分正方形的解组合起来以构建其父正方形的解因此，该算法依赖于树的深度，其为O（logL）。但包围输入的所有终端的最小正方形的大小可以任意大于最优解的值，这意味着任意大于N。另一个重要的问题是不要让终端位于解剖线上，而解剖线是入口所在的地方。为了克服这些问题，我们通过首先产生T的分区{Ti}i∈[k]来变换原始输入T，使得每个Ti具有长度取决于|我不是|.我们还表明，T的最优解可以建立从一个简单的工会的最优解为每个Ti。然后，我们通过缩放实例并将终端的坐标四舍五入到网格的中心来离散实例，飞机 这种转换的细节在第3节中给出。 让我们表示 由TJJ={TiJJ}i∈[k]变换的输入。我们的算法建立了一个表MR为每个解剖广场R。该表由R的有效配置索引，其编码R的细胞和门户的子分区。 我们在第5节中描述了这个概念。设π是R的一个有效构形。 该算法在MR[π]中保持一个最小长度解，它与构形π相容（定义见第5节），并符合（定义见第4节）平方R。如果L中的线段匹配，则构型π与解L相容由π描述的细胞和门户的划分。一致性定义是保持解决方案可行和简单（即低复杂性）所需的定义：线段形成循环，连接成对的终端，并且它们只在（恒定数量的）门户处穿过正方形为了写入条目MR[π]，算法访问已经为R的子剖分正方形建立的表。在所有可能的四个孩子的配置中，它只考虑了其中的一些，我们称之为与π一致的。从本质上讲，相容性保证了与这些子配置相容的相容解可以组合起来，建立一个与π相容的R的可行相容解。最后，我们证明了几个结果表明，我们的算法确实建立了一个可行的解决方案，TJJ和（1 +ε）-近似ESMC。其中一个主要的结果是，这种动态规划确实找到了最优的值。满足剖分平方根的TJJ的解（定理5.3）。另一个主要结果是存在一个解TJJ，它符合平方根，并且它的总长度与T的最优解的距离不太远（至多是ε的因子）（定理4.3）。C.N. Lintzmayer et al. /Electronic Notes in Theoretical Computer Science 346（2019）5895933限制性问题设R表示所有剖分正方形的集合。设CR、TR和PR分别是剖分正方形R的单元、终端和入口的集合，对于每个R ∈ R。为了简化符号，当我们提到一个剖分正方形R的单元、终端和入口的集合时，我们倾向于写C、T和P。令OPT（T）表示最优解，并且作为符号的滥用，表示最优解的成本，例如T。第一步是将实例转换为一个保证根分解平方的大小的实例。我们现在描述这样的转换，然后我们表明，它是可能的，以一个小的额外成本为原始实例构建一个解决方案。因此，我们的算法将在这样的转换实例上工作设T表示ESMC的一个实例。对于终端对的每个子集ST设μ（S）={ti，tJi：{ti，tiJ} ∈S}是底层终端的集合，设diam（S）是S中任何一对点之间的最大欧氏距离，即，S的直径。设G（T）表示顶点集为μ（T），边集为T的图.设dist（T）=max{ diam（V（H））：H是G（T）的一个分支}，即，必须连接的任何一对端子之间的最小距离。注意，每个可行解必须连接属于G（T）的同一个分量的端子。另一方面，人们可以很容易地构造一个可行的解决方案，连接每对终端{t，tJ} ∈ T与线段ttJ的两个副本。请注意，该解中的每条线段的长度最多为dist（T）。 因此因此dist（T）≤ OPT（T）≤ 2|不|dist（T）.（一）变换的第一步是划分终端的集合T，这是由算法1中给出的P分段执行的。命题3.1表明，这种划分的每个元素的最优解的并集给出了整个实例T的最优解。该分区允许我们结合分区的每个部分的直径，考虑其包含的端子对的数量和这些端子之间的最大距离。这个界限在命题3.2中给出。命题3.1 T的最优解是算法1在输入（T，T）上产生的划分中每个元素的最优解的并集，其中T是μ（T）的最小长度生成树。命题3.2算法1产生T的一个划分{Ti}i∈[k]，使得对于每个i∈ [k]，diam（μ（Ti））≤4|我不是|2 dist（Ti）.时间复杂度为O（n log n），其中n =|不|.证据Sketch. 第2行中的停止条件保证，对于每个i∈ [k]，μ（Ti）中的点允许生成树，其中每个线段的长度不超过2|我不是|dist（Ti）.这意味着存在一条长度至多为4的路径|我不是|2 dist（Ti）在μ（Ti）中的任何一对点之间。 我们证明了算法1中描述的分区过程可以在O（n log n）时间内实现，其中n =|不|.Q594C.N. Lintzmayer et al. /Electronic Notes in Theoretical Computer Science 346（2019）589√2算法1：分段输入：终端对的集合T和最小长度生成树T点集μ（T）输出：分割T1 设e是T如果长度（e）> 2，则为2|不|dist（T），则3设T1和T2为T−e4设Ti是Ti中终端对的子集，其中i∈ {1， 2}/*{T1，T2} 确实是T的一个分区 */5P←P分段（T1，T1）P分段（T2，T2）6其他7P← {T}8返回P现在我们有了实例T的一个划分{Ti}i∈[k]，我们的想法是我们的算法找到每个子集Ti的近似解，然后计算解的并集由于划分的每个元素与任何其他元素没有特别的不同为了简单起见，我们继续使用T作为输入实例（它代表分区的一个元素）。注意，根据3.2号提案，我们有diam（μ（T））≤ 4 n2dist（T）.（2）实例转换的第二步是离散化。在这里，我们认为在欧几里得平面中存在粒度为1的整数网格，即，将平面划分为边长为1的单元并且其线在整数点处相交的网格。这个想法是移动终端，它可以有任何坐标在最初的情况下，进入网格单元的中心。首先，我们将输入实例按（80n2）/（εdist（T））的因子缩放，得到TJ，这被称为缩放实例。通过等式（1）中给出的相同参数并考虑上述因子，我们现在有OPT（TJ）= OPT（T）εdist（T）≥80n 2.（三）ε此外，使用来自等式（2）的不等式，我们有diam（μ（TJ））= diam（μ（T））80n 2εdist（T）≤4n dist（T）80n 2εdist（T）320N32=ε.（四）离散化以在每个端子到网格单元的最近中心的位置上进行舍入而结束。设TJJ是对实例T j的终端位置进行四舍五入后得到的实例我们称TJJ为变换后的实例，它是在缩放和舍入μ（T）中的点后生成的。由于我们的算法适用于转换后的实例，引理3.3保证我们可以构造一个C.N. Lintzmayer et al. /Electronic Notes in Theoretical Computer Science 346（2019）58959540e∈L′′l∈G从转换后的实例中获得原始实例的解决方案，只需少量额外成本。引理3.3存在一个解，该解可以从T J J的任何解导出，且附加成本至多为（ε/40）OPT（T J）。如前所述，我们的算法适用于转换后的实例。目标是找到TJJ的近似最优解LJJ，使得LJJ与网格线相交的次数由L jj本身的长度限制，而LJJ本身又由常数乘以TJ的最优解的值限制。引理3.4存在解LJJ到TJJ，使得长度（LJJ）≤.1+εOPT（T J）和ε|埃布尔|≤ 3 OPT（T J），其中G是欧几里得平面上粒度为1的整数网格中的线的集合。我们的算法实际上会找到引理3.4中提到的解的近似。回想一下，L表示根剖分正方形的边长。接下来，我们给出L的值关于n的上界。首先注意边长为diam（μ（TJ））的平方是包围TJ的所有端点的最小值。因此，在本发明中，我们定义L为最小整数p的最小整数p，其至少为2直径（μ（TJ））。它由公式（4）得出L≤（1280n3 2）/ε。设A是2的最小整数幂，至少为30ε−1 logL。为每个水平（或垂直）解剖线l，l上的入口正好是l中x坐标（y坐标）为L/（A2深度（l））的整数倍的点。回想一下，每一个深度为i的正方形都被两条深度为i的分割线和两条深度小于i的分割线所包围。此外，深度为i的剖分正方形R的边长为L/2i。由于在深度为i的解剖线上，入口以L/（A2i）的整数倍放置，因此在A的每一侧最多有A个入口。因此，它认为，每个剖分正方形在其边界上最多有4个A门户也可以证明，对于每个剖分正方形R，R的所有角点是门户网站，除了点是根解剖广场的角落4近似 协调解设R是一个剖分正方形，其中R表示其边界，L是R中线段的有限多集。我们用ν（L）表示L中线段的所有端点的集合。对于每个点x∈v（L），δL（x）表示L中包含x的线段的数量。另外，设D=O（1/ε）是一个常数（在定理4.1中定义）。我们说L连通R的两点x，XJ，如果x和XJ属于L的同一连通分支。此外，L符合R，如果596C.N. Lintzmayer et al. /Electronic Notes in Theoretical Computer Science 346（2019）589L(i) LR至多包含4个（D+1）连通分支;(ii) L∈ R的每个连通分支都包含R的一个门;(iii) 对于每个胞腔x∈CR，最多存在一个L的分支与x也与R的边界相交;(iv) 对任意门函数p∈PR，有δL（p）≤2;(v) 对于每个点s∈ν（L）不是R的门，δL（s）是偶数;(vi) 如果正方形R中的一个端点t不通过L连接到它的配偶，那么t通过L连接到R的边界。图（1a）中描述了一个符合多重线段集的例子我们说L递归地符合R，如果它符合R和R的后代的所有剖分正方形。如果L递归地符合根剖分平方，则L被称为符合。在下文中，我们证明了ESMC协调解的存在性最大成本为（1 +ε）OPT（T）。我们从一个由引理3.4保证的可行解开始，然后我们将其变换为满足协调解的所有性质在期望的随机移位的解剖线，变换的初始解决方案增加其长度只有一个小的常数因子的最佳长度。定理4.1设T_JJ是原始实例T的变换实例，欧氏空间多目标问题。存在一个可行解L对于TJJ，其长度最多为（1 + 99ε/ 120）OPT（T），在边界框的随机移位上的期望L满足以下性质：每个剖分正方形R：(i) 对于R的每条边S，S至多有D个非角分量，其中D= 60ε−1;(ii) L∈ R的每个连通分支都(iii) 对于每个胞腔x∈CR，最多存在一个 L的分支相交X，并且还与R的边界相交;并且(iv) 如果R中的一个终端t不是通过L <$R连接到它的配偶，那么t通过L连接到R的边界。证据Sketch. 设LJJ为引理3.4给出的Tjj的可行解。注 意 ，L JJ平凡地满足性质（iv），因为它是T jj的可行解。 我们可以展示如何将L JJ变换为满足性质（i）、（ii）和（iii）的可行解L。 在所有这些变换中，我们只通过添加形成循环的线段集来增加L jj的已有分量。因此，我们可以很容易地证明性质（iv）在L中保持不变，并且对于每个点s∈ν（L），δL（s因此，L是满足性质（i）-（iv）的TJJ由于解的长度上的小的增加（细节省略），我们有长度（L）−长度（LJJ）≤（3ε/ 5）OPT（T）。通过将最后一个不等式与引理3.4中给出的界相结合，我们得到了长度（L）≤（1 +C.N. Lintzmayer et al. /Electronic Notes in Theoretical Computer Science 346（2019）589597⊆i=1i=1ε/40）OPT（T）+（3ε/ 5）OPT（T）≤（1 + 25ε/ 40）OPT（T）。Q推论4.2设T JJ是欧氏S-TEINER多目标问题的原始实例T的变换实例。 在边界框的随机移动范围内，存在长度至多为（1 + 99 ε/120）OPT（T）的Tjj的协调解.证据设L为定理4.1中给出的解。注意，L可以多次访问解剖方格的入口。 遵循同样的理念Arora在文献[1]中描述的最短解的一种形式，我们可以从L得到TJJ的一个协调解，其长度至多为length（L）≤（1 + 99ε/ 120）OPT（T）.Q定理4.3设T是欧氏空间S-TINERMULTIC_∞的一个实例。存在长度至多为（1+ε）OPT（T）的协调解，期望值超过边界框的随机移位证据设L是由Corol- lary 4.2保证的变换版本T jj的解。利用引理3.3，我们从L得到一个解LJ到T，使得长度（LJ）≤长度（L）+（ε/40）OPT（T）≤（1 + 102ε/ 120）OPT（T）.Q5该算法设S是一个集合，令S（S）表示S的幂集，即S的所有子集的集合。一个集合π称为S的一个子划分，如果π≠（S），并且π中的元素两两不相交设π和πJ是S的两个子分拆.我们说πJ是π的粗化，如果对每个PJ∈πJ，存在S<$π使得PJ=P∈SP。最后，对于每个元素s∈S，π（s）表示π中包含s的元素，如果有一个，否则是π。现在考虑一个剖分正方形R。设CR：TR→CR是一个函数，CR（t）是R中包含t的胞腔。为了简化，我们使用C来表示与剖分正方形R相关的函数。R的一个配置是一个元组（πIN，πOUT，θ），满足(i) πIN和πOUT是PR<$CR的子划分;(ii) πOUT是πIN的粗化;(iii) πIN的每个元素包含R的至少一个门和至少一个单元;并且(iv) 对于每个Q∈πIN，θ（Q）=.p1.. . p：{pi}Q ，如果l>1，则{pi}−1中的p项是成对不同的，也就是说，一个集合的s序列的点在Q。注意，如果l >1，则p1和pl可能是同一个入口R的一个构形（πIN，πOUT，θ）被称为有效的，如果下列成立。(i) |≤4（D + 1），Π ≤ 8（D + 1）个顶点;| ≤4(D+1),andπINco nt ainsatmost8(D+1)portals;(ii) 对任意Q∈πIN和门函数p∈Q，θ（Q）中存在一个包含p的序列;598C.N. Lintzmayer et al. /Electronic Notes in Theoretical Computer Science 346（2019）589、i=1 πi=1在i=1i=1i=1出来出来出来出来出来i=1，tals m aybe在u∈πIN和v∈π，IJN的交集中。我们在πIJN中定义π=分割{πi}t......这是什么？πt在在出来i=0(iii) 对于每对配对终端{t，TJ}，使得t∈TR，TJ∈/TR，则这对配对终端是一个Q∈π，使得CR（t）∈Q.对于每对配对端子{t，tJ}使得t，tJ∈TR，或者存在Q∈πOUT使得{CR（t），CR（tJ）}<$Q，或者存在{CR（t），CR（tJ）}<$Q =<$Q，对于所有Q∈ πIN。有效配置示例见图（1b每个解剖正方形都有4个A入口和B2单元，所以我们可以限制有效配置的推论5.1至多存在（ε−2log n）O（ε−2）个有效配置。设R和RJ是两个不同的平方。 设（πIN，πOU T，θ）和d（πIJN，πOJUT，θJ）分别为R和RJ的有效构型.我们用G（πIN，πIJN）表示πIN和πIJN的交图，其构造如下. G（πIN，πIJN）的顶点集是πIN<$πIJN，它的边集是{{u，v}：u <$v/=<$}。请注意，只有por-v∈V（K）v：K是G（πIN，πIJN）i=1不i=1=π在π我在.对于任何子集合，此外，我们用G（θ）表示门图，它的点集PR和边集{{u，v}：θQ∈π， 在s. t中.uv是θ（Q）中某个序列的子序列。注意，θ（Q）的每个元素定义G（θ）中的一条（闭或开）路，对所有的Q∈Π。考虑一个剖分正方形R0及其子剖分正方形R1、R2、R3和R4.对于每个i∈ {0，...，4}，设（πi，πi，θi）是Ri的有效构型.在出来此外，设λ = 4i设G=4G（θi）。 配置集{（πi，πi ，θi）}4 被称为相容的，如果它满足以下所有性质。(i) π0与通过以下过程从λ获得的集合相同。为每个P∈λ，从P中移除（4Pi）\ P0中的所有门户，并替换每个P中的单元格被R0的相应父单元格所取代。最后，从λ中移除不包含任何R0门户的元素。(ii) 对于eachQ∈λsuch，使得Q<$P0=λ，则G[Q<$（4Pi）]的eachcompp有欧拉循环(iii) 对于eachQ∈λsuch，使得Q∈P0=/λ，eachG[Q∈（4[i]有两个端点都在P0的欧拉路径。(iv) 对任意i∈ {1， 2， 3， 4}和任意x，y∈Pi<$Ci，πi(x) =πi(y) 当且仅当λ（x）=λ（y），或者存在R0的门p和q，使得0出来(p) =π0(q) ，λ（x）=λ（p）和λ（y）=λ（q）。(v) F或每对配对终端{t，tJ}满足t∈Ti和tJ∈Tj，其中i，j∈{1，2，3，4}，我们有λ（Ci（t））= λ（Cj（tJ）），或π0（Ci（t））= π0（Cj（tJ））。(vi) 对任意门函数p∈（4Pi）\P0，dG（p）是偶数，其中dG（p）是门函数的度p在G(vii) 对任意门函数p∈P0，d0（p）=dG（p）.(viii) 存在E（G）到一个边不相交路集合X的一个划分，π1在自然是有定义的。C.N. Lintzmayer et al. /Electronic Notes in Theoretical Computer Science 346（2019）589599(a)（b）第（1）款Fig. 1. 一个有终端ti和入口pj的剖分正方形R。 单元格由虚线示出。图（1a）显示了符合R的线段的多集合。较粗的线表示相同的线段（例如，在t1和p1之间）。图（1b）显示了R的有效配置（πIN，πOUT，θ）。R的端点和顶点分别为{t1，t2，t3，t4，t′4}和{p1，p2，p3，p4，p5}. πIN={Q1，Q2，Q3}，πOUT={Q1<$Q2，Q3}，θ（Q1）={p2p5}，θ（Q2）={p1}，θ（Q3）={p3p4}。以下财产。 K是G（θ0）的分支当且仅当存在一条路P∈ X，使得K与通过提升与V（P）\P0中的顶点关联的所有边并移除V（P）\P0中的所有顶点而从P得到的图相同.我们的算法的伪代码在算法2中给出。 它发现了转换实例的最优一致性解决方案。命题5.2和定理5.3被用来证明这个主张。设L和（πIN，πOUT，θ）分别是R的协调解和有效构型令Γ（L）表示L中线段所构成的所有可能路径的集合。我们将LJ定义为L中的线段集合，这些线段属于包含R的某个门户的分量。我们说门图G（θ）和L是相干的当且仅当存在一个内射函数f：E（G（θ））→Γ（ LJ）使得（i）对于G（θ）中的每条边uv，f（uv）是端点在门u和v上的线段的路径，（ii）对于每个l∈LJ，存在一个e∈E（G（θ））使得f（e）包含l.回想一下，G（θ）的每个分支都是一条（开或闭）路，因此，如果L和G（θ）是相干的，则G（θ）的所有分支的集合将LJ划分为连接R的门户的线段的路。我们说L和（πIN，πOUT，θ）相容当且仅当(i) 对于L的每个与R的边界相交的分量K，存在单个部分Q∈π，使得Q恰好由R中被K包围的细胞和门户组成;并且(ii) G（θ）和L是相干的。命题5.2对于每个协调解L到R，存在R的一个有效配置（πIN，πOUT，θ）与L相容。定理5.3设R是一个剖分正方形。算法2（即， S OLVE-ESMC）填充在表MR中，使得对于R的每个有效配置（πIN，πOUT，θ），MR[（πIN，πOUT，θ）]是与（πIN，πOUT，θ）兼容并递归地符合R的线的多集的最小长度。600C.N. Lintzmayer et al. /Electronic Notes in Theoretical Computer Science 346（2019）589在出来i=1i=1i=1在出来算法2：SOLVE-ESMC输入：解剖直角尺R和TR1如果R至多包含一个终端，则2对于 Rdo的每个有效配置（πIN，πOUT，θ）3MR[（πIN，πOUT，θ）]←0对于do中的每一部分Q∈π，如果Q中的单元格是连通的，并且这些单元格包含门户，Q，则6设LQ是包含在Q的胞腔中的最小长度的线集，使得LQ与G（θ）相干，包含Q中的终端（如果有的话），并且Q中的每个胞腔至多被LQ的一个与R的边界相交的分支穿过。如果没有这样的一套，定义长度（LQ）=+∞。7MR[（πIN，πOUT，θ）]← MR[（πIN，πOUT，θ）]+长度（LQ）8其他9MR[（πIN，πOUT，θ）]←+∞其他1011设R1、R2、R3和R4是R的四个子剖分方12SOLVE-ESMC（Ri）for eachi∈ { 1， 2， 3， 4}13对于Rdo的每个有效配置（πIN，πOUT，θ）14MR[（πIN，πOUT，θ）]←+∞15对于所有配置。R的（πIN，πOUT，θ）和{Ri}4 的{（πi，πi，θi）}4做16如果{（πIN，πOUT，θ）}<${（πi，πi ，θi）}4是相容的，则在外层17MR[（πIN，πOUT，θ）]←i=1min，MR[（πIN，πOUT，θ）]，π4Mi[（πi，πi，θi）]，命题5.4设T是具有n对终端的ESMC的实例，设R是包围T的终端的根剖分平方。 算法2（SOLVE- ESMC）在输入（R，T）上运行的时间复杂度为O（n log κn），其中κ∈ O（ε−2）。6结论和进一步研究设T是ESMC的一个实例，它包含n对终端，ε∈（0，1）. 我们在定理5.3中证明了所提出的算法发现，符合给定边界框的T的最小长度解。 在命题5.4中，我们论证了这样的解可以在O（nlogκn）时间内找到，其中κ是一个只依赖于ε的常数。在定理4.3中，我们证明了长度至多为（1 +ε）OPT（T）的在边界框的随机移位上的期望。由上述结果和马尔可夫C.N. Lintzmayer et al. /Electronic Notes in Theoretical Computer Science 346（2019）589601长度至多为（1 +ε）OPT（T），概率至少为一半。 因此，所提出的算法是一个随机近似计划的ESMC运行在准线性时间。在2011年，Bateni等人设计了平面图中Steiner森林问题的多项式时间近似方案（PTAS）[2]。因此，进一步研究的一个自然方向是研究平面图上Steiner多圈问题的PTAS的存在性。引用[1] 阿 罗 拉 ， S. ， Euclidean traveling salesman and other geometric problems 的 Polynomial timeapproximation schemes，Journal of the ACM45（1998），pp.753-782。[2] Bateni，M.，M. Hajiaghayi和D. Marx，Approximation Schemes for Steiner forest on planar graphsand graphs of bounded treewide，Journal of the ACM58（2011），pp.21：1-21：37。[3] Borradaile ， G. ， P. N. Klein 和 C. Mathieu ， A polynomial-time approximation scheme forEuclidean Steiner forest，ACM Transactions on Algorithms11（2015），pp.19：1-19：20。[4] 佩雷拉G.，M. C. S. Felice，P. H. D. B. Hokama和E. C. Xavier，Steiner多周期问题及其在协作卡车装载问题中的应用，在：第17届国际实验算法研讨会26：1-26：13。[5]Salazar-Gonzalez，J. J.， 斯坦纳循环多面体，欧洲运筹学杂志147（2003），pp. 671-679[6]Stein ov'a，M.，最小Steiner循环问题的应用可理解性，计算与信息学29（2012），pp. 1349-1357年。