Finite Dominating Sets for Rectilinear Center Problems with Polyhedral Barriers

  • In planar location problems with barriers one considers regions which are forbidden for the siting of new facilities as well as for trespassing. These problems areimportant since they reflect various real-world situations.The resulting mathematical models have a non-convex objectivefunction and are therefore difficult to tackle using standardmethods of location theory even in the case of simple barriershapes and distance funtions.For the case of center objectives with barrier distancesobtained from the rectilinear or Manhattan metric it is shown that the problem can be solved by identifying a finitedominating set (FDS) the cardinality of which is bounded bya polynomial in the size of the problem input. The resultinggenuinely polynomial algorithm can be combined with bound computations which are derived from solving closely connectedrestricted location and network location problems.It is shown that the results can be extended to barrier center problems with respect to arbitrary block norms having fourfundamental directions.

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:P.M. Dearing, Hamacher H.W., K. Klamroth
URN (permanent link):urn:nbn:de:hbz:386-kluedo-4871
Serie (Series number):Report in Wirtschaftsmathematik (WIMA Report) (45)
Document Type:Preprint
Language of publication:English
Year of Completion:1999
Year of Publication:1999
Publishing Institute:Technische Universität Kaiserslautern
Faculties / Organisational entities:Fachbereich Mathematik
DDC-Cassification:510 Mathematik

$Rev: 12793 $