Dominating sets for rectilinear center location problems with polyhedral barriers

Dominating sets for rectilinear center location problems with polyhedral barriers

0.00 Avg rating0 Votes
Article ID: iaor200487
Country: United States
Volume: 49
Issue: 7
Start Page Number: 647
End Page Number: 665
Publication Date: Oct 2002
Journal: Naval Research Logistics
Authors: , ,
Keywords: sets
Abstract:

In planner location problems with barriers one considers regions which are forbidden for the siting of new facilities as well as for trespassing. These problems are important since they model various actual applications. The resulting mathematical models have a nonconvex objective function and are therefore difficult to tackle using standard methods of location theory even in the case of simple barrier shapes and distance functions. For the case of center objectives with barrier distances obtained from the rectilinear or Manhattan metric, it is shown that the problem can be solved in polynomial time by identifying a dominating set. The resulting genuinely polynomial algorithm can be combined with bound computations which are derived from solving closely connected restricted location and network location problems.

Reviews

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