A comment on a minmax location problem

A comment on a minmax location problem

0.00 Avg rating0 Votes
Article ID: iaor20011175
Country: Netherlands
Volume: 23
Issue: 1/2
Start Page Number: 41
End Page Number: 43
Publication Date: Aug 1998
Journal: Operations Research Letters
Authors:
Keywords: computational analysis, networks
Abstract:

In a recent paper Hamacher and Schobel study a minmax location problem in the Euclidean plane that draws its main difficulty from the restriction that the new facility must not be placed within a so-called forbidden region. Hamacher and Schobel derive a polynomial time algorithm for this problem that runs in O(l3) time for inputs of size l. In this short note we argue that this location problem can be solved in O(l log l) time by applying standard techniques from computational geometry. Moreover, by providing a matching lower bound in the algebraic computation tree model of computation, we show that the time complexity O(l log l) is in fact the best possible.

Reviews

Required fields are marked *. Your email address will not be published.