A new solution approach for solving the 2-facility location problem in the plane with block norms

  • Motivated by the time-dependent location problem over T time-periods introduced in Maier and Hamacher (2015) we consider the special case of two time-steps, which was shown to be equivalent to the static 2-facility location problem in the plane. Geometric optimality conditions are stated for the median objective. When using block norms, these conditions are used to derive a polygon grid inducing a subdivision of the plane based on normal cones, yielding a new approach to solve the 2-facility location problem in polynomial time. Combinatorial algorithms for the 2-facility location problem based on geometric properties are deduced and their complexities are analyzed. These methods differ from others as they are completely working on geometric objects to derive the optimal solution set.

Download full text files

Export metadata

Metadaten
Author:Andrea Maier
URN:urn:nbn:de:hbz:386-kluedo-41282
Series (Serial Number):Report in Wirtschaftsmathematik (WIMA Report) (156)
Document Type:Preprint
Language of publication:English
Date of Publication (online):2015/07/24
Year of first Publication:2015
Publishing Institution:Technische Universität Kaiserslautern
Date of the Publication (Server):2015/07/24
Page Number:22
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