北大中文核心期刊
中国科学引文数据库（CSCD）来源期刊
中国科技核心期刊
入选数学领域高质量科技期刊
Scopus
EBSCO 

运筹学学报 ›› 2010, Vol. 14 ›› Issue (2): 23-36.

• 运筹学 • 上一篇    下一篇

区间图上可带负权的2-中位选址问题

程郁琨   

  • 出版日期:2010-06-15 发布日期:2010-06-15

The Pos/Neg-weighted 2-Median Problem on Interval Graphs

CHENG Yu-Kun   

  • Online:2010-06-15 Published:2010-06-15

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

Abstract: This paper deals with the facility location problem on interval graphs with ositive 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(n^2)$ time algorithms for both models of the 2-median problem have been developed.