论文部分内容阅读
新世纪信息技术和软件产业的一个显著的特征是计算机在网络环境中工作，依靠底层的通信链路交换信息.这就自然产生了越来越多的网络优化问题.这些问题通常是大规模的，需要快速求解.许多的网络优化问题被证明是NP难的.然而，我们必须在实践中处理这些问题.近似是处理NP难优化问题的一种成功的方法，近似算法致力于在多项式时间内给出问题的一个尽可能最优的解.对近似算法的研究不但是越过问题的NP困难性的一种方式，也是求解NP难优化问题的本质的方法.我们使用近似方法研究网络优化问题，对这些问题给出近似算法和证明问题的可近似性下界.
有两大类典型的网络优化问题.一类是网络设计问题(NetworkDesign)，这类问题关注的目标是将若干源-目标对(或终端集)连通起来.另一类是割集问题(Cut)，这类问题关注的目标是将若干源-目标对(或终端集)断开.从问题目标上看它们是相互对偶的.网络设计问题和割集问题在计算机网络、电信网络、运输流网络和集成电路设计等方面有着广泛的应用.具体而言，我们主要研究了如下四个方面的问题，它们是两类网络优化问题中的典型代表.
一、k-FacilityLocation问题(选址问题).给定若干设施位置点和需求点以及它们之间的距离，k-FacilityLocation问题询问如何以最小的费用在设施位置点打开最多不超过k个设施以满足所有需求点的需求.该问题是运筹学中的一个经典问题.使用局部搜索方法，对k-FacilityLocation问题给出了新的近似算法.通过对解的结构的深入分析，证明算法的近似比为2+(√3)+ε.该结果是关于k-FacilityLocation问题目前已知最好的近似比.
二、Min-Sum和Min-Max不相交路径问题(选路问题).Min-Sum不相交路径问题询问问题的一个解，连通所有的需求(源-目标对)，使所选取路径的总长度最短.Min-Max不相交路径问题询问连通所有需求的解，使所选取路径中最长路径的长度最短.在复杂性方面，证明了一般图上的Min-Sum不相交路径问题是FPNP完全的.在不可近似性方面，证明了只要P≠NP，对任意小的常数ε＞0，即使在平面图上Min-Sum不相交路径问题和Min-Max不相交路径问题不能够被近似到Ω(m1-ε)以内，其中m是图上边的数目.以上复杂性结果和不可近似性结果推广了前人的结果，并且这些结果是更强的，因为它们是在即使已知输入实例是可行的(即，已知输入实例存在连通全部需求的解)条件下被证明的.基于线性规划技术，对Min-Max边不相交路径问题和Min-Sum边不相交路径问题首次给出了Bicriteria近似算法.
三、k-SteinerForest问题(网络连通性问题).给定图上l个需求(源-目标对)，k-SteinerForest问题询问费用最小的解，连通其中至少k个需求.该问题是Hajiaghayi和Jain在SODA'06上提出的一个有趣的未解决问题.证明了贪心算法的一个复合引理，并由该引理推导出了k-SteinerForest问题的一个贪心算法，其近似比为O(min{n2/3，(√l)}logk)，改进了关于此问题文献已知最好近似比.并且，贪心算法的复合引理具有其一般性，可用于近似一类部分覆盖(PartialCover)类型的优化问题.
四、树上推广的Multicut问题(割集问题).提出并研究了树上推广的Multicut问题.给定树上l个终端集，树上推广的Multicut问题询问费用最小的一组边，使得在树上删除这组边能够断开所有的终端集.对该问题的Prizecollecting版本给出了近似比为3的原始-对偶近似算法和近似比为2.55的随机化近似算法，对该问题的k-版本给出了近似比为min{2(l-k+1)，k}的近似算法.找到了k版本的树上推广的Multicut问题和k-稠密子图问题之间的一个有趣的联系，从而证明将k-版本的树上推广的Multicut问题近似到O(n1/6-ε)以内是困难的，其中ε＞0是某个小的常数.
最后，我们指出改进k-FacilityLocation问题的近似比、设计树上k-SteinerForest问题的近似算法以及改进树上推广的k-Multicut问题的近似比是与本文工作密切相关的几个Open问题.