A new bound and an O(mn) algorithm for the undesirable 1-median problem (maxian) on networks
Published in Computers & Operations Research, 2005
Recommended citation: Colebrook M, Gutiérrez J, Sicilia J. "A new bound and an O(mn) algorithm for the undesirable 1-median problem (maxian) on networks". Computers & Operations Research 32(2), 309-325 (2005) https://doi.org/10.1016/S0305-0548(03)00238-7
Abstract
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.