An O(mn) algorithm for the anti-cent-dian problem

Abstract

The problem of locating an undesirable facility on a network under the anti-cent-dian criterion is addressed. Such criterion represents the convex combination of the undesirable center (maximize the minimum distance) and the undesirable median (maximize the sum of distances). To determine the optimal location point, we propose an efficient algorithm in O(mn) which improves a former approach proposed by other authors in O(mn log n) time. This new algorithm is based on a new upper bound and on some specific properties of the anti-cent-dian problem.