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

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

近几十年来，网络优化问题的反问题得到了国内外学者的广泛关注，成为最优化领域的一个重要课题，它同时也具有较大的实际意义与应用价值。网络选址是近年来最优化领域的一个热门课题，网络p-重心选址是其中的一类具有重要研究价值的问题，也是网络优化的一个重要分支，因此，网络p-重心选址的反问题成为网络优化反问题领域的一个重要课题，国内外许多学者在这些方面做了大量的研究工作。本项目主要从以下几方面对网络p-重心选址的反问题进行了系统的研究：1、研究了一些多项式时间可解的网络p-重心选址问题的反问题，通过分析问题的组合性质特征，设计出了其多项式时间算法或组合算法；2、对一些NP-困难的优化问题及网络p-重心选址反问题，用巧妙的构造方法证明了其NP-困难性，并得到了一些启发式算法或其特殊情形下的多项式时间算法；3、对区间线性规划问题进行了系统的研究，并研究了区间线性方程组和线性不等式的可解性与可行性。得到了一种求解线性规划问题的新方法，为线性规划问题的求解提供了新的理论基础；4、提出了一种广义的网络优化反问题的模型，得到了一些具有普遍意义的算法设计技巧，并设计出了相应的多项式时间算法。这些对网络优化反问题的算法设计和求解将起到较大的推进作用。值得一提的是，本项目研究成果中的1篇论文“Checking weak optimality of the solution to linear programming with interval right-hand side”入选了ESI高被引论文。