文章基本信息

标题：An Optimal Algorithm for the Weighted Median Problem
本地全文：下载
作者：Zhu, Daxin ; Wang, Xiaodong
期刊名称：Journal of Computers
印刷版ISSN：1796-203X
出版年度：2014
卷号：9
期号：2
页码：257-265
DOI：10.4304/jcp.9.2.257-265
语种：English
出版社：Academy Publisher
摘要：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.
关键词：Weighted median;facility location;binary search;pivot selection;linear time;optimal algorithm