Solving restricted line location problems via a dual interpretation

Solving restricted line location problems via a dual interpretation

0.00 Avg rating0 Votes
Article ID: iaor20001371
Country: Netherlands
Volume: 93
Issue: 1
Start Page Number: 109
End Page Number: 125
Publication Date: Jun 1999
Journal: Discrete Applied Mathematics
Authors:
Keywords: programming: geometric
Abstract:

In line location problems the objective is to find a straight line which minimizes the sum of distances, or the maximum distance, respectively, to a given set of existing facilities in the plane. These problems have been well solved. In this paper we deal with restricted line location problems, i.e. we have given a set in the plane where the line is not allowed to pass through. With the help of a geometric duality we solve such problems for the vertical distance and then extend these results to block norms and some of them even to arbitrary norms. For all norms we give a finite candidate set for the optimal line.

Reviews

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