摘要：Abstract本文研究了区间图上可带负权的2-中位选址问题.根据目标函数的不同,可带负权的p-中位选址问题(p≥2)可分为两类:即MWD和WMD模型;前者是所有顶点与服务该顶点的设施之间的最小权重距离之和,后者是所有顶点与相应设施之间的权重最小距离之和.在本篇论文中,我们讨论了区间图上可带负权2-中位选址问题的两类模型,并分别设计时间复杂度为O(n^2)的多项式时间算法.

摘要：在网络服务系统中,存在由于各种人为因素(恐怖行为、黑客袭击等)导致网络设施服务中断的情况。为抵御有预谋的攻击,需要更加重视如何识别网络系统中的关键设施。结合P-中位选址模型,以设施失效对网络系统运行效率影响最大化为目标,给出针对基于P-中位模型的网络关键设施识别问题(即R-中断模型),并针对该模型提出贪婪搜索、邻域搜索和禁忌搜索3种算法。结合Galvo、Europe 150和USA 263等大型的测试实例,对上述算法进行比较分析,得出禁忌搜索算法最有效的结论。最后,结合Europe 150数据的例子比较了P-中位问题与R-中断问题,认为在选址决策中事先考虑到人为攻击导致的中断问题可以增加网络的抗攻击能力,减少损失。