¹Faculty of Mathematics & Computer Science, Quanzhou Normal University, China
²Faculty of Mathematics & Computer Science, Fuzhou University, China

---

Abstract—In this paper, we consider the weighted rectilinear min-sum facility problem to minimize the sum of the weighted rectilinear distance between the given points and a new added point. The core problem is the problem in its one dimensional cases noted as the weighted median problem. We present efficient algorithms for optimally solving the weighted median problem. The computational experiments demonstrate that the achieved results are not only of theoretical interest, but also that the techniques developed may actually lead to considerably faster algorithms.

Index Terms—Weighted median, facility location, binary search, pivot selection, linear time, optimal algorithm

[PDF]

Cite: Daxin Zhu, Xiaodong Wang, "An Optimal Algorithm for the Weighted Median Problem," Journal of Computers vol. 9, no. 2, pp. 257-265, 2014.