网络链路选择问题的近似算法

本项目针对NP困难网络链路选择问题的近似算法和不可近似性这一专题开展研究。网络链路选择问题是处理网络连通性的一类网络设计问题，来源于人们对计算机网络和电信网络的底层通信网络的研究。链路选择问题是网络设计问题中的核心问题之一。近似算法是处理NP困难问题的一种本质的方法，关于链路选择问题近似理论的研究是近年来近似算法领域中一个显著的研究热点。本项目致力于对链路选择问题中的若干重要NP 困难问题设计快速有效的近似算法，以及探索它们的可近似性下界，这些问题包括Rent-or-Buy和Buy-at-Bulk等典型的链路选择问题。项目组将深度剖析问题及其解的结构和性质，考察问题之间的相互联系，从正负两个方面对链路选择问题的近似求解进行全面的分析与探索。项目的研究将进一步丰富网络链路选择问题的近似理论，并在实际应用领域中产生广泛的影响。

本项目针对NP困难网络链路选择问题和割问题的近似算法和不可近似性这一专题开展研究。网络链路选择问题关注如何在网络中选取最小费用的边子集将若干给定终端连接起来，割问题关注如何在网络上去掉最小费用的边子集将给定的若干终端断开。因此，网络链路选择问题和割问题是目标对偶的两类网络设计问题。近似算法是处理NP困难问题的一种本质的方法，关于链路选择问题和割问题近似理论的研究是近年来近似算法领域中一个显著的研究热点。本项目致力于对所研究问题设计快速有效的近似算法，以及证明它们的计算复杂性和不可近似性。.项目所取得的主要研究结果包括：（1）对一类部分优化问题给出了线性规划取整加贪心的近似算法设计方法，应用该方法，对树上推广的k-多重割问题、k-森林问题等给出了首个近似算法。该结果是近似算法设计方法上的创新，是项目组取得的最为显著的成果。（2）应用线性规划取整加贪心的近似算法设计方法，对选择Buy-at-Bulk网络设计问题给出了全新的近似算法，近似比为O(q^{1/2})。这是自从Awerbuch和Azar在1997年使用树分解的方法近似选择Buy-at-Bulk问题以来，近15年的时间里出现的该问题的首个不同于树分解方法的非平凡近似算法。（3）通过对一系列割问题的深入研究，得到了最小k-传导率问题和k-最稀疏割问题的首个近似算法结果，对Leskovec等人在社会网络社区识别中所采取的实验方法给出了首个理论解释。（4）使用线性规划技术，对标签割问题给出了改进的O((m / OPT)^{1/2})-近似算法和新的O(n^{2/3} / OPT^{1/3})-近似算法，在此OPT为问题的最优解值。并且，证明了算法所使用的线性规划的整性间隙至少是Omega((m / OPT)^{1/2-epsilon})，从而表明使用给定的线性规划，近似比O((m / OPT)^{1/2})是理论上所能达到的最好的结果。.项目组共发表SCI索引论文6篇，EI索引论文7篇，以及4篇已在线出版或接受的SCI待检索论文。这些论文发表在Discrete Applied Mathematics、Journal of Combinatorial Optimization等国际期刊和ISAAC、LATIN等国际会议上。项目的研究进一步丰富了网络设计问题的近似理论，并在实际应用产生潜在的影响。