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

项目名称： 网络链路选择问题的近似算法

项目编号： No.60970003

项目类型： 面上项目

立项/批准年度： 2010

项目学科： 自动化技术、计算机技术

项目作者： 张鹏

作者单位： 山东大学

项目金额： 30万元

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

中文关键词： 链路选择；割；网络设计；近似算法；组合优化

英文摘要：

英文关键词： Link Selection；Cut；Network Design；Approximation Algorithm；Combinatorial Optimization