zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Asymmetric distances, semidirected networks and majority in Fermat-Weber problems. (English) Zbl 1163.90038
Summary: The Fermat-Weber problem is considered with distance defined by a quasimetric, an asymmetric and possibly nondefinite generalisation of a metric. In such a situation a distinction has to be made between sources and destinations. We show how the classical result of optimality at a destination or a source with majority weight, valid in a metric space, may be generalized to certain quasimetric spaces. The notion of majority has however to be strengthened to supermajority, defined by way of a measure of the asymmetry of the distance, which should be finite. This extended majority theorem applies to most asymmetric distance measures previously studied in literature, since these have finite asymmetry measure. Perhaps the most important application of quasimetrics arises in semidirected networks, which may contain edges of different (possibly zero) length according to direction, or directed edges. Distance in a semidirected network does not necessarily have finite asymmetry measure. But it is shown that an adapted majority result holds nevertheless in this important context, thanks to an extension of the classical node-optimality result to semidirected networks with constraints. Finally the majority theorem is further extended to Fermat-Weber problems with mixed asymmetric distances.

90C35Programming involving graphs or networks
Full Text: DOI
[1] Albert, G. E. (1940). A note on quasimetric spaces. Bulletin of the American Mathematical Society, 46, 219. · doi:10.1090/S0002-9904-1940-07252-0
[2] Bourbaki, N. (1943). Topologie générale. Paris: Herman.
[3] Blumenthal, L. M. (1970). Theory and applications of distance geometry. Bronx: Chelseta Publ. Co. · Zbl 0208.24801
[4] Buchanan, D. J., & Wesolowsky, G. O. (1993). Locating a noxious facility with respect to several polygonal regions using asymmetric distances. Computers and Operations Research, 20, 151--165. · Zbl 0770.90037 · doi:10.1016/0305-0548(93)90071-P
[5] Carrizosa, E., & Rodriguez-Chia, A. M. (1997). Weber problems with alternative transportation systems. European Journal of Operational Research, 97, 87--93. · Zbl 0923.90111 · doi:10.1016/S0377-2217(96)00066-5
[6] Carrizosa, E., Conde, E., Munõz, M., & Puerto, J. (1997). Simpson points in planar problems with locational constraints. The polyhedral gauge case. Mathematics of Operations Research, 22, 297--300. · Zbl 0883.90076
[7] Cech, E. (1966). Topological spaces. London: Interscience.
[8] Cera, M., & Ortega, F. A. (2002). Locating the median hunter among n mobile prey on the plane. International Journal of Industrial Engineering, 9, 6--15.
[9] Cera, M., Mesa, J. A., Ortega, F. A., & Plastria, F. (2008). Locating a central hunter on the plane. Journal of Optimization Theory and Applications, 136(2), 155--166. · Zbl 1146.90462 · doi:10.1007/s10957-007-9293-y
[10] Chen, R. (1991). An improved method for the solution of the problem of location on an inclined plane. RAIRO Operations Research, 25, 45--53. · Zbl 0734.90053
[11] Deza, M. M., & Laurent, M. (1997). Geometry of cuts and metrics. Berlin: Springer. · Zbl 0885.52001
[12] Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269--271. · Zbl 0092.16002 · doi:10.1007/BF01386390
[13] Drezner, Z., & Wesolowsky, G. O. (1989). The asymmetric distance location problem. Transportation Science, 23(3), 201--207. · Zbl 0682.90037 · doi:10.1287/trsc.23.3.201
[14] Durier, R. R. (1990). On Pareto optima, the Fermat--Weber problem and polyhedral gauges. Mathematical Programming, 47, 65--79. · Zbl 0706.90066 · doi:10.1007/BF01580853
[15] Durier, R., & Michelot, C. (1985). Geometrical properties of the Fermat--Weber problem. European Journal of Operational Research, 20(3), 332--343. · Zbl 0564.90013 · doi:10.1016/0377-2217(85)90006-2
[16] Fliege, J. (1994). Some new coincidence conditions in minisum multifacility location problems with mixed gauges. Studies in Locational Analysis, 7, 49--60. · Zbl 0891.90095
[17] Fliege, J. (1997). Nondifferentiability detection and dimensionality reduction in minisum multifacility location problems. Journal of Optimization Theory and Applications, 94(2), 365--380. · Zbl 0889.90102 · doi:10.1023/A:1022635712721
[18] Fliege, J. (1998). A note on ’On Pareto optima, the Fermat--Weber problem, and polyhedral gauges’. Mathematical Programming, 84(2), 435--438. · Zbl 0949.90086 · doi:10.1007/s101070050030
[19] Fliege, J. (2000). Solving convex location problems with gauges in polynomial time. Studies in Locational Analysis, 14, 153--172. · Zbl 0974.90010
[20] Hakimi, S. L. (1964). Optimal location of switching centers and the absolute centers and medians of a graph. Operations Research, 12, 450--459. · Zbl 0123.00305 · doi:10.1287/opre.12.3.450
[21] Hiriart-Urruty, J. B., & Lemaréchal, C. (2001). Fundamentals of convex analysis. Berlin: Springer. · Zbl 0998.49001
[22] Hinojosa, Y., & Puerto, J. (2003). Single facility location problems with unbounded unit balls. Mathematical Methods in Operations Research, 58, 87--104. · Zbl 1116.90075 · doi:10.1007/s001860300277
[23] Hodgson, M. J., Wong, R. T., & Honsaker, J. (1987). The p-centroid problem on an inclined plane. Operations Research, 35(2), 221--233. · Zbl 0635.90029 · doi:10.1287/opre.35.2.221
[24] Idrissi, H., Lefebvre, O., & Michelot, C. (1988). A primal dual algorithm for a constrained Fermat--Weber problem involving mixed gauges. Recherche Operationnelle / Operations Research, 22, 313--330. · Zbl 0663.90026
[25] Idrissi, H., Lefebvre, O., & Michelot, C. (1989). Duality for constrained multifacility location problems with mixed norms and applications. Annals of Operations Research, 18, 71--92. · Zbl 0707.90071 · doi:10.1007/BF02097796
[26] Kaufman, L., & Rousseeuw, P. (1990). Finding groups in data. New York: Wiley.
[27] Kelley, J. (1975). General topology. New York: Springer. · Zbl 0306.54002
[28] Labbe, M., Peeters, D., & Thisse, J.-F. (1995). Location on networks. In M. Ball et al. (Eds.), Handbooks in OR & MS : Vol. 8. Network routing (pp. 551--624). Amsterdam: North-Holland. · Zbl 0862.90088
[29] Levy, J. (1967). An extended theorem for location on a network. Operational Research Quarterly, 18, 433--442. · Zbl 0152.38301 · doi:10.1057/jors.1967.73
[30] Lindenbaum, A. (1926). Contributions à l’étude de l’espace métrique. Fundamenta Mathematica, 8, 209--222. · Zbl 52.0585.01
[31] Love, R. F., Morris, J. G., & Wesolowski, G. O. (1988). Facility location: Models and methods. New York: Norh Holland.
[32] Michelot, C., & Lefebvre, O. (1987). A primal-dual algorithm for the Fermat--Weber problem involving mixed gauges. Mathematical Programming, 39, 319--335. · Zbl 0641.90034 · doi:10.1007/BF02592080
[33] Minieka, E. (1979). The chinese postman problem for mixed networks. Management Science, 25, 643--648. · Zbl 0423.90048 · doi:10.1287/mnsc.25.7.643
[34] Minkowski, H. (1911). Theorie der konvexen Körper, Gesammelte Abhandlungen (Vol. 11). Berlin: Teubner.
[35] Mirchandani, P. B. (1975). Analysis of stochastic networks in emergency service systems, IRP-TR-15-75, Operations Research Center, Massachusetts Institute of Technology, Cambridge, MA, USA.
[36] Nickel, S. (1998). Restricted center problems under polyhedral gauges. European Journal of Operational Research, 104, 343--357. · Zbl 0955.90071 · doi:10.1016/S0377-2217(97)00189-6
[37] Nickel, S., Puerto, J., & Rodriguez-Chía (2003). An approach to location models involving sets as existing facilities. Mathematics of Operations Research, 28, 693--715. · Zbl 1082.90059 · doi:10.1287/moor.28.4.693.20521
[38] Papini, P., & Puerto, J. (2005). Location problems with different norms for different points. Jouranl of Optimization Theory and Applications, 125, 673--695. · Zbl 1127.90049 · doi:10.1007/s10957-005-2095-1
[39] Plastria, F. (1984). Localization in single facility location. European Journal of Operational Research, 18, 215--219. · Zbl 0546.90031 · doi:10.1016/0377-2217(84)90187-5
[40] Plastria, F. (1987). Solving general continuous single facility location problems by cutting planes. European Journal of Operational Research, 29, 329--332. · Zbl 0608.90022 · doi:10.1016/0377-2217(87)90198-6
[41] Plastria, F. (1992a). GBSSS, the generalized big square small square method for planar single facility location. European Journal of Operational Research, 62, 163--174. · Zbl 0760.90067 · doi:10.1016/0377-2217(92)90244-4
[42] Plastria, F. (1992b). On destination optimality in asymmetric distance Fermat--Weber problems. Annals of Operations Research, 40, 355--369. · Zbl 0783.90061 · doi:10.1007/BF02060487
[43] Plastria, F. (1992c). A majority theorem for Fermat--Weber problems in quasimetric spaces with applications to semidirected networks. In J. Moreno (Ed.), Proceedings of the sixth meeting of the EURO working group on locational analysis (pp. 153--165). Tenerife, Spain: Puerto de la Cruz.
[44] Plastria, F. (1994). Fully geometric solutions to some planar minimax location problems. Studies in Locational Analysis, 7, 171--183. · Zbl 0891.90108
[45] Ribeiro, H. (1943). Sur les espaces a métrique faible. Portugalia Mathematicae, 4, 21--40. · Zbl 0028.19103
[46] Rinow, W. (1961). Die innere Geometrie der metrischen Räume. Berlin: Springer (in German). · Zbl 0096.16302
[47] Rockafellar, T. (1970). Convex analysis. Princeton: Princeton University Press. · Zbl 0193.18401
[48] Ward, J. E., & Wendell, R. E. (1985). Using block norms for location modeling. Operations Research, 33, 1074--1090. · Zbl 0582.90026 · doi:10.1287/opre.33.5.1074
[49] Wendell, R. E., & Hurter, A. P. Jr. (1973). Optimal locations on a network. Transportation Science, 7, 18--33. · doi:10.1287/trsc.7.1.18
[50] Witzgall, C. (1964). Optimal location of a central facility, mathematical models and concepts. Report 8388, National Bureau of Standards, Washington DC, USA.
[51] Witzgall, C. (1965). On convex metrics. Journal of Research of the National Bureau of Standards -- B. Mathematics and Mathematical Physics, 69B(3), 175--177. · Zbl 0135.34403