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

本项目针对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等国际会议上。项目的研究进一步丰富了网络设计问题的近似理论，并在实际应用产生潜在的影响。