A new bound and an O(mn) algorithm for the undesirable 1-median problem (maxian) on networks

摘要

The problem of locating an undesirable facility on a network with n nodes and m edges so as to maximize its total weighted distance to all nodes is addressed. We propose a new upper bound to the problem. Likewise, we develop a new algorithm in O(mn) time which dynamically updates this new upper bound. Computational results on low and high dense networks, as well as planar networks, are presented.