可带负权的图的p-中心和p-中位问题

图的中心和中位问题是图论与组合最优化理论研究的重要内容，它在选址、通讯、复杂网络和环境科学等领域中有着广泛的应用。与经典的中心和中位问题比较，国际上最近提出的可带负权的图的中心和中位问题在实际中更具有普遍意义。本项目侧重以图论和组合最优化为工具来开展对可带负权的图的中心和中位问题的研究，讨论其算法实现问题。研究的主要内容为：(1)在具有特殊结构的赋权图上，设计该类问题的多项式时间算法；(2)探索这些问题在一般赋权图上的近似算法实现。在研究方法上侧重图的结构性质的深入分析，并充分结合组合最优化方法，力争在理论方法上有新的突破。本课题将首次考虑该类问题的近似算法。对这些问题的研究，将推动图论、组合最优化、选址科学和复杂网络的交叉研究与发展，同时对一些实际问题的解决也具有一定的理论指导意义。

图的中心(center)和中位(median) 问题是选址科学的两个核心问题，也是图论与组合最优化理论研究的重要内容，在通讯、复杂网络、运输和环境科学中有着广泛应用。国际上最近提出的可带负权的图的中心和中位问题在实际中更具有普遍意义。本项目侧重以图论和组合最优化为工具来开展对可带负权的图的中心和中位问题的研究，讨论了其算法实现问题。我们取得的主要成果如下：(1)关于p-maxian问题，讨论了对块图、区间图和仙人掌图几类图的p-maxian问题。对具有单位边长的块图p-maxian问题，证明了除3阶完全图外，块图的p-maxian问题是线性时间可解的；其次，给出了具有任意权区间图的p-maxian问题的线性时间算法；对区间图的任意权2-中位问题,若目标为MWD和WMD目标，分别给出了时间O(n2)的多项式算法；最后，我们证明了仙人掌图的2-maxian问题具有时间为O(n2)的多项式时间算法。(2)讨论了客户具有子图结构的可带负权p-中位问题，对具有单位边长块图的1-中位问题，若中位限制在图的顶点上，我们提出了该问题的一个线性时间算法；对客户具有子树结构的p-中位问题, 分别给出了树的1-中位问题和2-中位问题的多项式时间算法.（3）讨论了可带负权的p-中心问题的研究。p-中心问题是指在网络中放置p个设施，使得每个客户到达最近设施的最大权距离最小。证明了块图的无权1-中心问题是线性时间可解的。对服务设施以一定概率失效的选址问题，证明了区间图的备份2-中心问题是线性时间可解的。