| 区间图上可带负权的2-中位选址问题（英文） |
| |
| 引用本文： | 程郁琨.区间图上可带负权的2-中位选址问题（英文）[J].运筹学杂志,2010(2):23-36. |
| |
| 作者姓名： | 程郁琨 |
| |
| 作者单位： | [1]上海大学数学系,上海200444 [2]浙江财经学院数学与统计学院,杭州310018 |
| |
| 摘 要： | Abstract本文研究了区间图上可带负权的2-中位选址问题.根据目标函数的不同,可带负权的p-中位选址问题（p≥2）可分为两类：即MWD和WMD模型;前者是所有顶点与服务该顶点的设施之间的最小权重距离之和,后者是所有顶点与相应设施之间的权重最小距离之和.在本篇论文中,我们讨论了区间图上可带负权2-中位选址问题的两类模型,并分别设计时间复杂度为O（n~2）的多项式时间算法.
|
| 关 键 词： | 运筹学 选址问题 中位问题 可带负权 区间图 |
The Pos/Neg-weighted 2-Median Problem on Interval Graphs |
| |
| Authors: | Cheng Yukun |
| |
| Institution: | Cheng Yukun (1. Department of Mathematics, Shanghai University, Shanghai 200444, China; 200444. 2. School of Mathematics and Statistics, Zhejiang University of Finance and Economics, Hangzhou 310018, China) |
| |
| Abstract: | This paper deals with the facility location problem on interval graphs with positive and negative interval weights. We consider two different objective functions： the sum of the minimum weighted distances （MWD） of the intervals from the facilities and the sum of the weighted minimum distances （WMD）. Two O（n2） time algorithms for both models of the 2-median problem have been developed. |
| |
| Keywords: | Operation research location theory median problem semiobnoxious facil-ity interval graph |
| 本文献已被 维普 等数据库收录！ |
