An O(mn) algorithm for the 1-maximin problem on a network

This paper addresses the problem of locating a point on a general network with n vertices and m edges, so as to maximize the minimum weighted distance from the point to the vertices (l-maximin). Based on several properties, it is shown that there exists a unique local l-maximin point on each edge and therefore at least one but no more than m l-maximin points on the network. An efficient O(mn) algorithm for finding the optimal set is developed and implemented on a PC. Computational results and a numerical example are provided. (C) 1999 Elsevier Science Ltd. All rights reserved.