连通与设施选址问题的近似算法研究

In the development of economy, the timeliness and accuracy of the information are particularly important. Therefore research in connectivity of network has profound influence on practical applications. Since most problems in network design are NP-hard, approximation algorithm is therefore one of the most important methods to solve them. The project will consider the combination of two fundamental problems, namely the Steiner tree problem and the facility location problem. Steiner tree, an essential structure in network connectivity, has extensive applications in such areas as very large scale integrated circuits (VLSI), wireless network, etc. On the other hand, facility location problem, originating in factories and warehouses locating, is a fundamental problem in computer science/operations research with modern applications in such areas as base station design and location of network server agents. But the connectivity of single source-sink version can no longer meet more and more complex network design requirements. This project, based on the research on the Steiner tree problem and the facility location problem, proposes combining the Steiner tree problem and facility location problem into the so-called connected facility location problem along with its various extensions and adopting the techniques of approximation algorithm to solve them. These techniques include linear program rounding or randomized rounding (especially introducing the random variables following non-uniform distribution), primal-dual scheme, dual-fitting, and local search, etc.

随着经济的发展, 信息的及时性和准确性显得尤为重要, 因此网络中的连通性研究对实际应用有着深远的影响, 而网络设计中的大部分问题都是NP困难的, 近似算法是研究这类问题的重要方法之一. 斯坦纳树是网络连通结构中最基本的一类结构, 在超大规模集成电路(VLSI), 无线网络等领域中都有广泛的应用. 而设施选址问题也是计算机科学和运筹学中的一类基本问题, 起源于工厂, 仓库等位置的确定, 在现代社会的基站设计, 网络服务器代理的安置中也有广泛的应用. 但随着网络结构越来越复杂, 单点对之间的连通已经不能够满足生产需求. 本项目在斯坦纳树问题和设施选址问题的基础上, 从近似算法的角度研究将连通性与设施选址问题相结合的问题- - 连通设施选址问题及其推广形式. 设计近似算法时需要用到下面的技巧, 线性规划舍入或随机舍入(尤其是引入服从非均匀分布的随机参数), 原始对偶, 对偶拟合, 和局部搜索等.

本项目围绕网络设计中具有深刻现实意义的NP-难问题，从近似算法角度进行研究。研究的问题主要包括设施选址问题，斯坦纳树问题，图划分问题，半定规划和鲁棒优化等, 均取得了预期研究成果。并且在研究上述问题过程中很好地将不同问题的算法设计技巧相融合，对后续研究提供了更多的思路和启发。在本项目支持下共发表期刊论文26篇(其中SCI检索论文17篇)，会议论文9篇。. 随着科学技术的发展，信息的及时性、准确性和大数据性扮演的角色日益重要，在以前的研究中认为切合实际的模型变得日益远离实际。本项目对当今科技水平下的诸多现实问题抽象出了更加贴切也更加广义的模型，在前人研究技巧上加以创新和推广，提出了我们的新型近似算法。. 我们研究了带线性和次模惩罚的设施选址问题，将此前的最好近似比1.8526和2.5分别改进到了1.5148和2。论文被中国、美国、波兰、荷兰、巴西、日本等多国学者引用28次，其中包括麻省理工学院Retsef Levi、哥伦比亚大学Adam N. Elmachtoub、弗罗茨瓦夫大学Jaroslaw Byrka等，该结果迄今为止仍未被改进。我们提出和研究了带惩罚的一般设施选址问题并设计了其7.88-近似算法, 随后此结果被我们改进到了5.83。 此外, 我们研究了多阶段设施选址问题，随机设施选址问题，容错设施选址问题，平方度量设施选址问题和k-设施选址问题等。斯坦纳树问题上，我们主要研究了其奖励收集模型，分别设计了广义奖励收集斯坦纳森林问题的原始对偶近似算法和奖励收集的k-斯坦纳树问题的5-近似算法。 在算法设计的技巧研究方面，我们得到了鲁棒优化的分布式机会约束的安全近似，最小化次模函数和半定舍入设计近似算法方面的部分结果. 作为技巧的延伸，我们还研究了图划分和无关机排序的部分变形问题。