Abstract
Given a metric space with a set of given facilities, location theory asks to place a new facility which minimizes the distances to the given ones. Many results for a variety of problems with norms or metrics as distances are known in the space \({\mathbb {R}}^n\). This paper handles specific location problems in \({\mathbb {R}}^n\) that have been induced from location problems in the so called phylogenetic tree space coming from an application in biology. Some of the location problems in this space may be transformed to \({\mathbb {R}}^n\) and carry interesting properties. In this paper, we only focus on the resulting problems in \({\mathbb {R}}^n\) and we call them fixed gate point problems. The twist is that one is only allowed to traverse between two orthants by going through a fixed gate point, which induces interesting distances. In this paper, these problems are investigated for three different objective functions and solution methods in form of closed formulas and algorithms are given.
Similar content being viewed by others
References
Alizadeh F, Goldfarb D (2003) Second-order cone programming. Math Program 95(1):3–51
Billera LJ, Holmes SP, Vogtmann K (2001) Geometry of the space of phylogenetic trees. Adv Appl Math 27(4):733–767
Blanco V, Puerto J, Ponce D (2017) Continuous location under the effect of ‘refraction’. Math Program 161(1–2):33–72
Brimberg J, Kakhki HT, Wesolowsky GO (2003) Location among regions with varying norms. Ann Oper Res 122(1–4):87–102
Brimberg J, Kakhki HT, Wesolowsky GO (2005) Locating a single facility in the plane in the presence of a bounded region and different norms. J Oper Res Soc Jpn 48(2):135–147
Carrizosa E, Rodríguez-Chía AM (1997) Weber problems with alternative transportation systems. Eur J Oper Res 97(1):87–93
Drezner Z, Shelah S (1987) On the complexity of the Elzinga–Hearn algorithm for the 1-center problem. Math Oper Res 12(2):255–261
Elzinga J, Hearn DW (1972) Geometrical solutions for some minimax location problems. Transp Sci 6(4):379–394
Fathali J, Zaferanieh M (2011) Location problems in regions with lp and block norms
Franco L, Velasco F, Gonzalez-Abril L (2012) Gate points in continuous location between regions with different l-p norms. Eur J Oper Res 218(3):648–655
Kuhn HW (1973) A note on Fermat’s problem. Math Program 4(1):98–107
Kuo C-H, Wares JP, Kissinger JC (2008) The apicomplexan whole-genome phylogeny: an analysis of incongruence among gene trees. Mol Biol Evol 25(12):2689–2698
Mitchell JSB, Papadimitriou CH (1991) The weighted region problem: finding shortest paths through a weighted planar subdivision. J ACM 38(1):18–73
Nickel S, Puerto J (1999) A unified approach to network location problems. Networks 34(4):283–290
Nickel S, Puerto J (2006) Location theory: a unified approach. Springer Science and Business Media, New York
Nye TMW (2015) Convergence of random walks to Brownian motion in phylogenetic tree-space, arXiv preprint. arXiv:1508.02906
Owen M (2011) Computing geodesic distances in tree space. SIAM J Discrete Math 25(4):1506–1529
Owen M, Provan JS (2011) A fast algorithm for computing geodesic distances in tree space. IEEE/ACM Trans Comput Biol Bioinform (TCBB) 8(1):2–13
Parlar M (1994) Single facility location problem with region-dependent distance metrics. Int J Syst Sci 25(3):513–525
Plastria F (2019) Pasting gauges I: shortest paths across a hyperplane. Discrete Appl Math 256:105–137
Zaferanieh M, Kakhki HT, Brimberg J, Wesolowsky GO (2008) A BSSS algorithm for the single facility location problem in two regions with different norms. Eur J Oper Res 190(1):79–89
Acknowledgements
The author gratefully acknowledges the funding of this work by the Deutsche Forschungsgemeinschaft in the framework of the Research Training Group 2088 and thanks Anita Schöbel for helpful suggestions for the paper. Moreover the author thanks three anonymous referees for their helpful suggestions to improve the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Botte, M. Fixed gate point location problems. TOP 29, 547–582 (2021). https://doi.org/10.1007/s11750-020-00551-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-020-00551-4