A Finite Dominating Set Algorithm for a Dynamic Location Problem in the Plane
- A single facility problem in the plane is considered, where an optimal location has to be identified for each of finitely many time-steps with respect to time-dependent weights and demand points. It is shown that the median objective can be reduced to a special case of the static multifacility median problem such that results from the latter can be used to tackle the dynamic location problem. When using block norms as distance measure between facilities, a Finite Dominating Set (FDS) is derived. For the special case with only two time-steps, the resulting algorithm is analyzed with respect to its worst-case complexity. Due to the relation between dynamic location problems for T time periods and T-facility problems, this algorithm can also be applied to the static 2-facility location problem.
Author: | Andrea Maier, Horst W. Hamacher |
---|---|
URN: | urn:nbn:de:hbz:386-kluedo-40174 |
Series (Serial Number): | Report in Wirtschaftsmathematik (WIMA Report) (155) |
Document Type: | Preprint |
Language of publication: | English |
Date of Publication (online): | 2015/03/05 |
Year of first Publication: | 2014 |
Publishing Institution: | Technische Universität Kaiserslautern |
Date of the Publication (Server): | 2015/03/05 |
Page Number: | 16 |
Faculties / Organisational entities: | Kaiserslautern - Fachbereich Mathematik |
DDC-Cassification: | 5 Naturwissenschaften und Mathematik / 510 Mathematik |
MSC-Classification (mathematics): | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization |
Licence (German): | Standard gemäß KLUEDO-Leitlinien vom 13.02.2015 |