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

项目名称： 连通与设施选址问题的近似算法研究

项目编号： No.11371001

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 徐大川

作者单位： 北京工业大学

项目金额： 62万元

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

中文关键词： 设施选址；斯坦纳树；图划分；半定规划；鲁棒优化

英文摘要： 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, ap

英文关键词： Facility location；Steiner tree；Graph partition；Semi-definite programming；Robust optimization