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 w ith 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, i t is shown that there exists a unique local l-maximin point on each edge an d 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 pro vided. (C) 1999 Elsevier Science Ltd. All rights reserved.