Operations Research Transactions ›› 2010, Vol. 14 ›› Issue (2): 23-36.

• Original Articles • Previous Articles     Next Articles

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

CHENG Yu-Kun   

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

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.