UNIVERSITÄTSBIBLIOTHEK

Multifacility Location Problems with Tree Structure and Finite Dominating Sets

  • Multifacility location problems arise in many real world applications. Often, the facilities can only be placed in feasible regions such as development or industrial areas. In this paper we show the existence of a finite dominating set (FDS) for the planar multifacility location problem with polyhedral gauges as distance functions, and polyhedral feasible regions, if the interacting facilities form a tree. As application we show how to solve the planar 2-hub location problem in polynomial time. This approach will yield an ε-approximation for the euclidean norm case polynomial in the input data and 1/ε.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Andrea Maier, Thomas Ullmert, Horst W. Hamacher
URN (Permalink):urn:nbn:de:hbz:386-kluedo-51562
Dokumentart:Preprint
Sprache der Veröffentlichung:Englisch
Veröffentlichungsdatum (online):13.02.2018
Jahr der Veröffentlichung:2018
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):13.02.2018
Seitenzahl:25
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 510 Mathematik
Lizenz (Deutsch):Creative Commons 4.0 - Namensnennung, nicht kommerziell, keine Bearbeitung (CC BY-NC-ND 4.0)