关于一些网络最优化问题的近似算法的研究

摘要

随着网络和网络技术的高速发展，很多网络上的最优化问题被提出.不幸的是，很多这些问题都被证明是NP-完备问题.这就意味着，目前这些问题不可能在多项式时间内得到最优解.因此，研究者们就致力于寻找这些NP-完备问题的近似算法.
　　 本文主要研究了斯坦纳树问题和连通控制集问题及它们变形的近似算法.这些问题都是网络中经典的最优化问题，同时也是经典的NP-完备问题.特别地，在单位圆盘图上，这些问题依然是NP-完备的.对于这些问题，我们都给出了近似算法，并对算法进行了理论分析，给出了算法的近似比.
　　 本文共分为三章.第一章首先介绍了图论中的一些基本概念和记号.然后，介绍了计算复杂度理论的一些基本概念.接下来，我们给出了近似算法的基本概念，并通过顶点覆盖问题和它的一个的近似算法为例，对其巾的一些概念进行了解释.最后，罗列了本文得到的主要结论.
　　 第二章主要研究了斯坦纳树问题变形的近似算法.给定一个边赋权图G=(V,E)和边权函数c，及terminal集X(∪-)V，斯坦纳树问题的目标是寻找一棵权重最小且连接terminal集巾所有顶点的树.斯坦纳树问题是一个经典的最优化问题和NP-完备问题.在本章的开始，我们将介绍斯坦纳树问题并综述其研究进展.
　　 在第二章的第二节，我们研究了一个斯坦纳树问题的变形，selected-internal斯坦纳树问题.给定一个边赋权完全图G=(V,E)和边权函数c，及两个子集x'(∪-) X(∪-)V满足｜x-x'｜≥2，selected-internal斯坦纳树问题是在图G中寻找一棵最小的子树T连接X中的所有顶点，并且X'巾的所有顶点均不是T的叶子节点.假设c是度量函数，本节得到了此问题的一个近似比为(1+ρ)的近似算法，在这里ρ是目前为止斯坦纳树问题最好的近似比.
　　 对于给定的一个顶点赋权图G=(V,E)和顶点赋权函数ω，及terminal集X(∪-)V，顶点赋权斯坦纳树问题的目标是寻找一棵总权重最小且连接所有terminal集中顶点的树.我们将在第二章余下的内容中在单位圆盘图上研究这个问题.在第二章的第三节，首先利用支撑树方法，本文得到了一个近似比为5的近似算法.然后，通过将权重从顶点转移到边，给出了一个近似比为2.5ρ的近似算法.最后，假设terminal集是c-local的，我们证明了单位圆盘图上的顶点赋权斯坦纳树问题存在多项式时间的近似模式.也就是说，对于任意的ε＞0，总存在一个近似算法满足其近似比为l+ε.
　　 第三章将研究单位圆盘图上的连通控制集问题及其变形.给定图G=(V,E)，称顶点子集C(∪-)V是一个连通控制集，如果：1)对于任意的顶点υ∈V-C，υ总存在邻点在C中;2)导出子图G[C]是连通的.连通控制集问题的目标是寻找图G中一个包含顶点个数最少的连通控制集.第三章的第一节首先介绍了这个问题的背景及研究进展.然后，给出了计算连通控制集的基本思路.
　　 第三章的第二节考查了极大独立集(MIS)与最小连通控制集的关系.由于每个MIS都是控制集且可在多项式时间内得到，因此研究者们经常通过寻找MIS并连接它们来得到一个连通控制集.所以，MIS的大小与最小连通控制集大小之间的比值就在近似比分析中起着关键的作用.在本节中，借助于Voronoi图和欧拉公式，我们改进了这个比值，从而也就改进了所有基于这种方法的近似算法的近似比.
　　 第三章的第三节研究了单位圆盘图上的d-hop连通控制集.首先，对于一种特殊情况，2-hop连通控制集(TCDS或2-CDS)，我们提出了一个分布式的算法.然后，证明了算法输出结果的大小不会超过17.421opt+51.456，这里opt表示2-CDS问题最优解的大小.最后，对于任意的整数d，通过推广TCDS算法，使其成为了一个d-CDS的常数近似比的近似算法.
　　 第三章的第四节研究了赋权连通控制集问题，一个连通控制集问题的变形.利用已有的结论并结合顶点赋权斯坦纳树问题的PTAS算法，本文得到了单位圆盘图上此问题的一个近似比为5+ε的近似算法.接下来，我们将研究的方向从二维平面扩展剑三维空间，即研究单位圆球图上的连通控制集问题.利用贪心的方法，得到了一个近似比为13+ln10的近似算法.最后，对文章进行了总结并讨论了未来的工作方向.