小Manhattan网络的算法复杂性研究.docVIP

最小Manhattan网络的算法复杂性研究 计算机学院 郭泽宇 指导教师 孙贺 摘要：本文研究了最小Manhattan网络的复杂性和近似算法。通过给出3-可满足问题的基于部件的归约，本文证明了最小Manhattan网络是强NP-完全的，从而解决了这一长达十年的未知问题。此外，本文描述了一个时间复杂度为O(nlogn)的2-近似算法。该算法在运行时间和近似度上都达到目前最优。 关键词：NP完全性 近似算法 计算几何 Abstract: In this paper, we have studied the complexity of Minimum Manhattan Network and its approximations. Using a gadget-based reduction from 3-SAT, we showed that Minimum Manhattan Network is strongly NP-complete, which was open for ten years. Moreover, we have described a 2-approximation algorithm with time complexity O(nlogn), which has the best time complexity and approximation ratio up to now. Keywords: NP-completeness, Approximation Algorithm, Computational Geometry 引言 由于在城市规划，网络路由，分布式计算，大规模集成电路设计以及计算生物学[8]等众多领域的应用，J. Gudmundsson等人在文献[5]中首先提出了最小Manhattan网络(MMN)问题。该问题的描述为：对于平面上给定的若干个点，设计出由直线段构成的网络，使得任意两点间存在Manhattan路径（即由直线段构成且长度最短的路径），并在满足此条件的前提下使得网络总长度达到最短。 由于两点间Manhattan路径的长度同时也是L1范数下两点间的距离，可以看出，最小Manhattan网络问题等价于求L1范数下最小1-spanner的问题。更一般的t-spanner问题参见[4]。 在文献[5]中，作者提出了如下的三个重要问题：(1) MMN是否是NP-难的；(2) 是否存在该问题的PTAS近似方案；(3) 是否存在该问题的2-近似算法。同时，作者提出了一个时间复杂度为O(n3)的4-近似算法和一个时间复杂度为O(nlogn)的8-近似算法。此后，研究者们提出了一系列具有更优近似度和更低时间复杂度的近似算法[1,2,3,9,10,11]，其中[9,10]的证明是有缺陷的。本文作者也提出了基于动态规划的时间复杂度为O(n2)的2-近似算法[6]和基于贪心策略的时间复杂度为O(nlogn)的2-近似算法[7]，后者在近似度和时间复杂度上都达到了已知的最优。 本文作者通过给出从3-SAT到MMN的归约，证明了这一问题是强NP-完全的，从而解决了它的复杂性问题。本文的前半部分将着重介绍这一归约，后半部分则用于描述[7]中的2-近似算法。 1 预备知识 对于平面上两点p, q，p.xq.x定义R(p, q)为以p, q为对角顶点的矩形区域（矩形可能退化成一条线）。定义垂直无限区域BV(p, q)为p,q间的垂直无界区域{(x,y)|p.x=x=q.x}。类似地，我们将BH(p,q)定义为p,q间的水平无限区域。 记输入点集为T，对于T中的两点p,q, p.yq.y，如果在区域BV(p,q)-{(x,y)|x=p.x,y= p.y}-{(x,y)|x=q.x,y=q.y}中不含T中的任何点，则称R(p,q)为一个垂直带。类似地可给出水平带的定义。特别地，当p.x=q.x或p.y=q.y时，我们称这个带是退化的。图1给出了一个水平带的实例。图中点t位于q的右侧，因而不违反水平带的定义。 图1 水平带 对于平面中的点p，记Qk(p)为平面上以p为原点，代表第k象限的区域（含坐标轴）。 例如Q1(p)={(x,y)| p.x=x,p.y=y}。 2 归约框架 我们的主要目标是将一个由n个变量、m个子句组成的布尔公式ψ转换成顶点集T，使得ψ是可满足的当且仅当存在一个T上的最小Manhattan网络G，其总长度不超过一个多项式时间可计算的函数Q。 首先，在Manhattan网络中，我们可以用垂直和水平的带上的Manhattan路径来表示变量的赋值。如图2所示，实线代表赋值为1，虚线代表赋值为0。 图2 Manhattan路径与变量的赋值 其次，我们使用了若干部件(gadget)来完成归约。归约