英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料

三边连通的三正则图中TSP问题的一个改进上界

David Gamarnik, Moshe Lewenstein, Maxim Sviridenko

计算机科学系，巴伊兰大学，323室，邮箱50，巴基斯坦52900，以色列

IBM T. J. Watson研究中心，约克敦海茨，邮箱218，纽约10598，美国

2004年1月20日收到； 2004 年9月3日公布

摘要

我们认为旅行商问题（TSP）中的（度量完备的）3边连通三正则图是有趣的，因为他们的最优解和子回路消除LP松弛之间的联系。我们的主要结论是找出一个比3 / 2近似算法更好的求解一般性tsp问题的近似算法。

copy;2004 Elsevier公司保留所有权利

关键字: 近似算法;旅行商问题;图;正则图

1.介绍

在本文中，我们研究众所周知的旅行商问题。给定一个完全无向图 =（V，）与非负边权重，目标是（根据权重）找到一个访问每个顶点一次的最短封闭回路。访问每个顶点一次的闭路也被称为一个哈密顿回路。

一般情况下TSP问题是NP完全问题，不可逼近任何常数。即使TSP的度不同，其中的边权重形成的一个度超过顶点集，被称作MAXSNP-hard[8]。然而，Christofides[5]介绍了一个简洁的近似算法,该算法可以产生用于度量TSP问题的3 / 2近似因子 。近三十年后，仍然没有一个比Christofides的 3 / 2因子好的近似算法。在[7][6]中，Lawler et. al做了一个关于TSP的成果和历史详细的调查。

设G是边权重不违反三角不等式的任意图形。G上一个度量完成是指将完整的图形G加入一个完整的图中，使得每个附加边（u，v）以加权的方式让形成度量。最短路径度量完成是指一个为u和v之间的最短路径中的每条边增加指定重量的度量。由于在本文中我们只考虑最短路径度量完成，我们将把它们作为度量完成。在一般情况下，在本文中我们研究的是当G是一个三边连通三正则图时，是其度量完成。原图的所有边权重为1。

一个用来解决tsp问题的整数规划经典的公式如下:

我们用表示整数规划的最优解，用表示它的值。如上所述，我们发现是NP完全问题。改变条件（4），让产生一个线性规划使整数规划松弛也被称为子回路消除松弛(SER为短的子回路消除松弛)。

（对于类型(3)）尽管有指数数量受限制的缺点，仍然可以用一个多项式时间来计算SER，因为每个数据库分离的圈就是一个最小割的计算。我们用表示SER的解,用表示它的值。一种用于求SER解的近似质量的方法叫做最坏性能比（整性间隙）。

其中是SER解的一个值， 它的最大值超过了度量TSP问题的所有实例。

迄今为止最知名的结果是显示上限为。然而，没有已知的例子显示就是3/2。众所周知也是目前最好的就是，在图1中出现的下界。完整的例子就是这个图中的一个度量完成。为了算出4/3间隙，设图1中权重2的边为1/2，设权重1的边为1。对于所有的其它边，设= 0。图中的数字显示了最佳遍历路线。

图1.当rho;是4/3时的一个例子

这产生了以下关于的推论。

推论: 为了度量TSP问题，SER的完整性间隙为4/3。

已经有无数的尝试证明这一猜想属实;然而，到目前为止，这些尝试都没有成功。事实上，到目前为止猜想不仅没有被证明，甚至在3/2近似因子上也没有改进。这就要提出反问：也许3/2是可以实现度量TSP问题的最佳因子，或者说问题有一个小小的改变会让

成为最合适的结果。

在下面的理论中，子回路消除LP的最优解和三正则K边连通图是密切相关的。考虑到LP的最优解，我们为每个边e，定义变量最小的共同倍数为D。即对于每个边e，D满足D是整数。我们在顶点集V中的u和v之间，定义一个含有D边的多重图，其中e=（u，v）。这个多重图是由LP约束的二边连通的二正则图。原图G之后作为TSP问题的实例来完成度量。所有边的权重为1，即它是不加权。如果LP的最优值是n，即G是“部分的”哈密尔顿的话，那么这将足以找到的值 且，这将改善Christofides算法在特殊（但很常见）案件中的运用。

我们可能考虑满足上述特性的最简单的类图，权重为1的三正则（即3-regular）3边简单连通图。这些度量完成的简单图具有的权重，可以是相当大的。这点可以从在这类图中的中看出。事实上，请考虑以下解决方案：如果，则。否则。这种解决方案的可行性，是在存在图表G是三正则的且是3边连通的基础上。因为这个值是n，n是的一个很小的下限。这个解决方案是最佳的 。

因此，提高最优哈密尔顿圈边界的值，将足以证明在中令，一个哈密尔顿圈的重量最多为。在本文中，我们设计了一个多项式算法，这个多项式算法发现中一个哈密尔顿圈的重量最多是。可在[1][2][3][8]中找到，在度量空间中其他特殊类的近似算法中，带有性能保证的逼近算法好于3/2（甚至PTASes）。

对我们的结果有几个可能的改进方向。可想而知，对于一般的r-regular图，可以获得3/2近似的改进。另一种可能性是获得稀疏图的改进结果，假设图的最大度是3。在这一点上，我们甚至不能解除3边连通限制。

2.准备工作

考虑3边连通三正则图G和相应完整加权图。在相同权重访问所有顶点至少一次的情况下，中任何哈密尔顿圈对应于G中的一些封闭的回路。相反，在相同权重的情况下，任何这样的路径对应于中的一个哈密尔顿圈。因此，我们最初发现的在中找到最短哈密尔顿圈的问题可以改写成找到一个带有最小边数的欧拉图，且这个欧拉图在顶点集V中只使用G中的边(可能不只一次)。

设是一个图，是边的集合。设，...，是按照的连通分量组成的顶点的分区。根据是一个多重图可知G的收缩性，其中，且因为每个原始边，所以包含一个边，其中，。 注意G中的边和中的边之间是一一对应。还要注意，在中有可能有平行边。

在连通图G中有一个生成树。我们称之为多重图，其中包含E中每条边的两个拷贝和一个双重生成树。当我们根据T生成一个双重生成树时，我们称之为double T。

一个圈覆盖是指节点不相交的圈涵盖了一个图中的所有点的集合。下面这个结论是1891年Petersen[9]提出的。它的证明可以在Behzad, Chartrand and Lesniak-Foster[4]中找到。

引理1（Petersen[9]）设是一个2边连通三正则图。边集E可以分割成一个完美匹配M和一个圈覆盖C。

需要注意的是，找到一个完美匹配和一个圈覆盖都是多项式可解的。利用这个结果我们可以得出以下引理。

引理2设是3边连通三正则图。边集E可被划分成一个完美匹配M和一个无三角形的圈覆盖C（即一个圈覆盖不含有长度为3的圈）。

证明. 我们通过归纳图G的大小来证明引理。如果则引理没有价值。假设所有的图G中（注意必须是偶数）则我们证明了这个理论。考虑一个图G 中有。如果G不包含三角形，然后通过引理1可知图G可分成一个圈覆盖C（必须是无三角形的）和匹配M。否则，令是任意的三角形，并让是根据中G的收缩而收缩。仍然是具有n-2个顶点的3边连通三正则图，因此，可以被拆分成一个匹配和一个无三角形的圈覆盖C。请注意，通常当收缩，有平行边且因此循环时，才可能成立。然而，当G是3边连通图时这不会发生。收缩的三角形属于C中长度至少大于等于4的圈。如果我们不让收缩，我们可以从添加两个边到圈中，并在原始图G中得到一个长度为的圈。三角形中其余的边被添加到匹配图中。

3.TSP近似算法

3.1.算法概要

我们目前采用的算法是通过引理2的说明将边集合E的分区放入中。（我们只对C有兴趣，而不是M。）C是一个无三角形的圈覆盖。因此，C中每个圈长度至少是四。显然，如果正好有一个圈在圈覆盖内，这就是一个哈密尔顿圈，我们便完成了。同样地，如果所有的圈是相对比较大的，然后可以花费小小的“成本”将其转化成一个哈密尔顿圈。该算法考虑两种情况。首先很大一部分圈的大小是5或更大（我们称之high-five属性----将在后面定义）。如果圈覆盖C是大于五的那么我们可以从以下事实中得到----有很多大（长度大于4）的圈，可以利用这个可以在“降低成本”的条件下发现一个哈密尔顿圈。

当圈覆盖C不是high-five那么情况将会更难解决。C中包含了许多长度为4的圈。在这种情况下，我们将C放入圈的集合中，以将其从一个欧拉游历变成一个欧拉图。这是该算法的核心，并且可以用一种改进的近似因子的方式来进行。

3.2.high-five属性

在整个算法演示中，我们将一个常量设置在整个分析的最后。需要注意的是，如上所述， C中的圈越大越接近一个“真实”的TSP问题。下面的定义抓住有许多大圈的概念。

high-five属性：我们说如果在C中至少有个顶点且有长度为五或更大的圈，则称这个圈覆盖有high-five属性。其中n是V中顶点的数目。

让我们根据引理2选择边集的分区。我们将主要研究圈覆盖C。我们首先考虑的情况是，C的长度是大于五的。然后，更加困难的情况是，当C不是大于五的。最后，我们选择作为大于五和不大于五的圈覆盖之间合适的平衡点。因此，我们将证明下面的定理。

定理3.给定任意3边连通三正则图，该图的度量完成包含一个重量最多为的哈密尔顿圈。

3.3.大于五的圈覆盖

当圈覆盖C是大于五的，可以直接表明将得到一个比Christofides3/2近似值更好的改进。这种改进取决于并且如下所示。

引理4.如果圈覆盖C是high-five的，则有一个重量最少为的哈密尔顿圈。

证明.根据C令为G的收缩。 令T为上一个生成树。由T的两倍获得。得到。显然是欧拉图，因为它是连通的并且所有顶点具有一定的度，因此，其对应于中的一个哈密尔顿圈。
我们现在估计的边数。根据C中长度为4的圈令为顶点覆盖的集合。由于C满足high-five属性，且，因此上述游历的总权重可由以下公式估：

3.4.不超过五的圈覆盖

我们现在考虑的情况下圈覆盖C不超过五，即，当。令为C中圈长度刚好为4的边。根据，设为G的收缩。我们首先声明不包含自循环，否则将包含图2中的子图，也因此不是3边连通的。所以包含个四度顶点和个三度顶点。中共含有条边。

... ...

图2.在一个三边连通图中不可能含有4圈。

3.4.1.消除孤立的2圈

在收缩图中有许多节点对应于G中一个孤立节点，因此在圈覆盖G中仍然有3度节点对应于C中长度为4的圈节点。很容易验证这些节点有4度。此外，我们可能得中的平行边。

一个两圈是由两个平行边组成的图。如果它与其他的2圈没有一个公共的顶点，我们称之为2圈。对于G中每个独立的2圈，删除2圈中两个平行的边中的一条（注意，在中不能有三个平行的边，因为否则G不会是3边连通的）。令是一个新图。由于隔离的2个圈不接触彼此，被删除的边形成中一个匹配。因此中的边缘总数是至少为

3.4.2.删除两圈中的链和圈

很有可能在中一些两圈共享一个节点。然而，不超过2个两圈可以共享一个节点，因为在中顶点的度最多为4。事实上，只有一个节点入射在两个两圈上，没有其它边可以入射其上。我们认为这样的节点是2圈饱和。由于每个2圈饱和节点恰好入射到两个两圈上，2圈饱和节点形成（不相交的）（2圈中的）链和圈的集合。我们也称2圈饱和节点为内部节点，因为他们必须在链或圈的内部。但是，请注意2圈是唯一可能包含所有顶点的圈。这是因为在此圈中的所有节点都是2圈饱和的，因而不会入射到其它任何边，这意味着2圈的圈是的一部分。然而，是一个连通图。(图.3)。

图3. 2圈中链的组成

用表示链上所有的2圈。对于每条链中的2个顶点，在任一端，不是2圈饱和的。因此，尾边入射到一个或两个其它边。我们删除和G中的尾边。当恰好存在2圈中的一个圈是，我们让是一个包含每个2圈中一个边的哈密尔顿圈。在这种情况下，我们要从中的删除哈密尔顿路径。删除这些边后，不再包含2圈了。

我们现在（贪婪地）在G找到中任何圈 ，从图中删除它的边然后所有边入射到这个圈，之后将这个圈添加到 。我们重复这个过程，直到图G成为无圈图。

设p是在上述方法中的一些步骤（圈和链）且是在步骤i所定义的链或圈顶点的数量。在上述算法的最后，至多含有个不孤立的顶点。由于是无圈图且无平行边。即，一个森林最多有条边。从中删除的每一个圈或链中，最多有3条边。因此

因此

现在，考虑原来的，即我们根据删除边之前的图形。按照令为G的收缩 。从中的移走自循环,并让T成为中的一个生成树。

我们估计中顶点的总数 ，这个数比生成树T的大小多一个，也等于中顶点的数目减去中圈和链中顶点的总数，并加上的圈和链数。即

其中，表示树T边的数量。对于所有，第二不等式遵循。

3.4.3.最终的欧拉图

现在我们在图G中建立最终的欧拉图。让图成为图G中的边，并且和来自图的边一致（需要注意的是，即使现在我们已经改变了图G，但是每一步用的边都是来自原始的图G，因此，虽然图被定义在一个转换图中，但是这些边仍然来自原始图G）。我们将会改变图让所有顶点的度数都能满足欧拉图的需求。我们也要保证新的欧拉图最多包含条边，并且图的连通性不被破坏。也就是说，每个转换图的连通分量都是原始图的连通分量，反之亦然。然后我们改变图来保持“均匀度”要求，我们需要添加一个加倍生成树T来连接图中所有的连通分量，来保持“均匀度”的要求。因此，图将是欧拉图。

3.4

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[29557]，资料为PDF文档或Word文档，PDF文档可免费转换为Word