网络p-重心选址反问题的复杂性与算法研究

项目名称： 网络p-重心选址反问题的复杂性与算法研究

项目编号： No.11171316

项目类型： 面上项目

立项/批准年度： 2012

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

项目作者： 王勤

作者单位： 中国计量学院

项目金额： 52万元

中文摘要： 网络选址是近年来最优化领域的一个热门课题，网络p-重心选址是其中的一类具有重要研究价值的问题，也是网络优化的一个重要分支。近几十年来，网络优化问题的反问题得到了国内外学者的广泛关注，网络p-重心选址的反问题已成为该领域的一个重要课题，它同时也具有较大的实际意义与应用价值。国内外许多学者在这些方面做了大量的研究工作，但是对于该类问题的多项式时间算法及近似算法设计方面的研究还有待进一步突破。本项目将着重从以下几方面对网络p-重心选址的反问题进行系统地研究：1、研究不同范数下特殊结构中网络p-重心选址反问题的算法复杂性，寻找多项式时间最优算法或多项式时间逼近算法；2、对于NP-难的网络p-重心选址反问题，研究其可多项式时间近似的程度，设计出具有较好性能比的近似算法；3、建立具有普遍意义的算法设计方法和基本理论，在计算复杂性分析、多项式时间算法和近似算法的设计等方面做出具有一定创新性的研究成果。

中文关键词： 反问题；p-重心选址；区间线性规划；多项式时间算法；NP-困难性

英文摘要：

英文关键词： inverse problem；p-median location；interval linear programming；polynomial-time algorithm；NP-hardness